再帰的メソッドのトレース

Question

再帰の概念を理解するのは非常に混乱しています。私は再帰関数をトレースしようとしています。誰かが私を助けてくれますか？

public static int h(int n){ 
     if (n == 0) 
      return 0; 
     else 
      return h(n-1)+1; 
    } 

私は生成された結果は、実際に来ているか理解しない

int a = h(5); 
System.out.println(a) 

を書くのか？

Answer 1

まず第一に、あなたは再帰の概念を理解することの難しさを持っている場合、私は以下のリンクがお手伝いします思う：

• Recursion Programming
• Introduction to Recursion and Memoization with Examples:
• Recursion made simple
• Recursion

あなたは、デバッグファどのように動作しているかをIDEで確認することができます。ビークポイントを設定する方法や、デバッガを使用してプログラムを実行する方法については、Googleにお問い合わせください。

hについては、あなたが入力として与えたものを返します（正の数または0の場合）。また、大きな数字&が負の数の場合、StackOverflowErrorが発生します。作業を知るには、メソッド内でprintステートメントを使用することができます。

public static int h(int n) { 
    System.out.println("h(" + n + ")"); 
    if (n == 0) { 
     System.out.println("value: 0"); 
     return 0; 
    } else { 
     System.out.println("going down"); 
     int temp = h(n - 1) + 1; 
     System.out.println("h(" + n + ") --> " + temp); 
     return temp; 
    } 
} 

意志出力：

h(5) 
going down 
h(4) 
going down 
h(3) 
going down 
h(2) 
going down 
h(1) 
going down 
h(0) 
value: 0 
h(1) --> 1 
h(2) --> 2 
h(3) --> 3 
h(4) --> 4 
h(5) --> 5 

上記の出力は、作用を示すために編集することができる。

h(5) 
| going down 
|----h(4) 
| | going down 
| |---h(3) 
| | | going down 
| | |---h(2) 
| | | | going down 
| | | |--h(1) 
| | | | | going down 
| | | | |----h(0) 
| | | | | | value: 0 --> return 0; 
| | | | | h(1) --> 1 --> h(0) + 1 = 0 + 1 = 1 
| | | | h(2) --> 2   h(1) + 1 = 1 + 1 = 2 
| | | h(3) --> 3    h(2) + 2 = 1 + 1 = 3 
| | h(4) --> 4     h(3) + 3 = 1 + 1 = 4 
| h(5) --> 5      h(4) + 4 = 1 + 1 = 5 

次の方法hの非再帰的バージョンです。

public static int nonh(int n) { 
    int result = 0; 
    for (int i = n; i > 0; i--) { 
     result += 1; 
    } 

    return result; 
} 

:)

Answer 2

この再帰呼び出しをデバッガでトレースするには、ifステートメントにブレークポイントを設定し、プログラムを実行します。ブレークポイントに到達すると：

• をコールスタックウィンドウでn、
• ルックの値を調べます。

コールスタック上のアイテムの数は、再帰呼び出しごとに増加します。 nの値は1つ下がります。複数のレベルのコールがある場合は、コールスタック上のさまざまなアイテムをクリックします。コールサイトに移動します（return h(n-1)+1）。このレベルのスタックでnの値を調べることができます。

Answer 3

ロギングを試してください。または、よく、ちょうどデバッグ印刷は：

public static int h(int n){ 
    System.out.println("called h(" + n + ")"); 
    if (n == 0) { 
     System.out.println("we know the result for 0, returning 0"); 
     return 0; 
    } else { 
     System.out.println("we don't know the result, calling for " + (n-1)); 
     int t = h(n-1); 
     System.out.println("Found the result for " + (n-1) + 
          ", calculating the result for " + n); 
     return t + 1; 
    } 
} 

n = 4ために、あなたが得られます。

called h(4) 
we don't know the result, calling for 3 
called h(3) 
we don't know the result, calling for 2 
called h(2) 
we don't know the result, calling for 1 
called h(1) 
we don't know the result, calling for 0 
called h(0) 
we know the result for 0, returning 0 
Found the result for 0, calculating the result for 1 
Found the result for 1, calculating the result for 2 
Found the result for 2, calculating the result for 3 
Found the result for 3, calculating the result for 4 

は、それはあなたの手掛かりを与えるでしょうホープ - 何が起こるか見て、異なるアルゴリズムと遊びます。

さらに、h(-1)に電話してみてください。楽しんでください！