Javaでの再帰の理解

Question

Javaでの再帰アルゴリズムに基づいて、次のコードを理解するのに苦労しています。私は理解していない、異なる値xとyは、お互いに呼び出すときに持っているものは何ですか？コード内でSystem.out.print()を呼び出して正しい値を取得しようとしましたが、依然として助けになりません。

public class RecursionExample 
{ 

    private static int[][] arr={ 
     {3}, 
     {7, 4}, 
     {2, 4, 6}, 
     {8 ,5, 9, 3} 
    }; 

    public static int maxSum(int[][] graph, int x, int y, int sum) { 
     if (x == 3) 
     { 
      return sum+graph[x][y]; 
     } 
     int max= Math.max(maxSum(graph, x+1, y, sum), maxSum(graph, x+1, y+1, sum)); 

     sum += graph[x][y]; 
     return sum+max; 
    } 

    public static void main(String[] ar) 
    { 
     System.out.println(maxSum(arr,0,0,0)); 
    } 
} 

私はプログラミングのマスターではなく、私はJavaを学ぶことを試みています。どんな助けもありがとうございます。

Answer 1

番号ピラミッドの特定の番号へのリンク先のxおよびy値。あなたのアルゴリズムは何

は、2つの小さなものに大きなピラミッドを分割、上位桁に追加することによって、ピラミッドダウン最大パスを見つけることである：

{7}, 
    {2, 4}, 
    {8 ,5, 9} 

と

{4}, 
    {4, 6}, 
    {5, 9, 3} 

。

それから、小さなピラミッド（私は一番上でそれを行います）上の同じプロセスを行います。

{2}, 
    {8 ,5} 

と

{4}, 
    {5, 9} 

を。

これらのピラミッドを壊すと、2つの数字が残されているので、それを返すことがわかります。スタックを登ると、返された値が比較され、大きな値が返されます。

最終的には、ピラミッド内のすべてのトレイルを無差別にチェックすることでトップに到達します。彼らは、引数だとして

（ちなみに、同じ問題がprojecteuler.netである）

Answer 2

xとyの値は簡単です - ちょうどmaxSumに多くのコールを見て：最初に彼らは0です1つ前のステップで次のステップx + 1とy + 1（とx + 1とy）の各ステップでxが3になると停止するので、テーブルやツリーを作る：

0, 0 
    1, 1 
    2, 2 
     3, 3 
     3, 2 
    2, 1 
     3, 2 
     3, 1 
    1, 0 
    2, 1 
     3, 2 
     3, 1 
    2, 0 
     3, 1 
     3, 0 

...それだけです！

Answer 3

これは、基本的に、3回目の繰り返し（）に達するまで、自分自身を呼び出し続けます。

だから、ここフロー（各インデントがmaxSumへの呼び出しである）（マイナスmax内maxSumへの2つの呼び出しが簡単のため...）です：

x = 0 
y = 0 
sum = 0 

x != 3 

    x = 1 
    y = 0 
    sum = 0 

    x != 3 

     x = 2 
     y = 0 
     sum = 0 

     x != 3 

      x = 3 
      y = 0 
      sum = 0 

      x == 3 
      return 0 + 8 //graph[3][0] == 8 

     max = 8 //previous return 
     sum = 0 + 2 //graph[2][0] == 2 
     return 10 //max + sum == 8 + 2 == 10 

    max = 10 
    sum = 0 + 7 //graph[1][0] == 7 
    return 17 

max = 17 
sum = 0 + 3 //graph[0][0] == 3 
return 20 

Answer 4

何が起こっているかを理解するための最も簡単な方法は、再帰的な関数は、鉛筆と紙を取り出し、基本的な場合（x == 3のとき）になるまで各ステップを書くことです。その後、そこから逆方向に作業し、前の手順で戻り値を差し込みます。あなたがここにいるのは、頭部再帰です。ランタイムが各ステップを解決し、各ステップから元の呼び出しに戻るまで、戻ります。