メモリスタックは、バックツーバック再帰呼び出しをどのように探しますか？

Question

私は再帰の概念を理解しようとしています。私は、バイナリツリーの深さを計算するために、このようなコードがどのように機能するかを理解しない

（例階乗）コード内の1つの再帰的な文がある場合、それがどのように機能するかを理解する：

public int getDepth(Node root) 
{ 
    if (root == null) return 0; 

    int left = getDepth(root.left); 
    int right = getDepth(root.right); 
    if (left > right) 
     return left + 1; 
    else 
     return right + 1; 
} 

私はなぜ見ますこれは動作しますが、方法は動作しません。誰かが私に2番目の再帰呼び出し（getDepth（root.right））の仕組みを説明することはできますか？このコードはメモリ内でどのように見えますか？ getDepth（root.left）が呼び出されると再帰的に呼び出されると、スタックはすべての底のif文に移動しますか？

Answer 1

getDepthへの連続した呼び出しは完全に分離されており、したがってバインドされた変数は別々であり、引数に従い、異なる引数でそれ自身のバージョンから呼び出されているのを忘れています。

getDepth(null)を実行すると、最初の行の基本ケースのため0になります。ただし、getDepth(new Node(null, null))を送信すると、getDepth(null)と同じで、leftとrightの両方に0になり、結果は0 + 1となるgetDepth(root.left)が呼び出されます。

あなたは変数nodeに前のノードを結合して、getDepth(new Node(node, node))をしようとした場合、それらの両方は、このように、2

結果は 1 + 1だろう前のテスト1の答えになるところそれが再び両方 leftと rightを行います

このように続けて、前の計算に基づく結果を仮定することができます。複雑な議論から見て、各連続的な再帰が引数で新しく始まり、それは同じパターンに従うと想像する必要があります。結果が返されると、呼び出し元は次の行に進みます。

 1 
    /\ 
    2 3 
    /\ /\ 
4 5 6 7 

私はちょうどノードに番号を付け、ヌルノードは含めませんでした。実行はこの順番で行われます。識別情報は、スタックの深さ/再開を待っているコールの数を示します。

getDepth(1) 
    getDepth(2)   // left 
    getDepth(4)  // left 
     getDepth(null) // left base 
     getDepth(null) // right base 
     return 0 
    getDepth(5)  // right 
     getDepth(null) // left base 
     getDepth(null) // right base 
     return 0 
    return 0 + 1; 
    getDepth(3)   // right 
    getDepth(6)  // left 
     getDepth(null) // left base 
     getDepth(null) // right base 
     return 0 
    getDepth(7)  // right 
     getDepth(null) // left base 
     getDepth(null) // right base 
     return 0 
    return 0 + 1; 
    return 1 + 1; 
return 2 + 1; 

Answer 2

ツリーが単一のノード（ルートノードのみ）で構成されている場合は、実行をトレースしてみてください。 getDepth(root.left)が呼び出されたときに

スタックは次のようになります。

--->getDepth(root) // this is your entry point 

、スタックの一番上にある方法：

--->getDepth(root.left) //this will return 0 immediately, and will be popped of the stack 
    getDepth(root) // this is your entry point 

一度、getDepth(root.left)リターンを、スタックは次のようになります今度はどこから実行されたのでしょうか（今はgetDepth(root.right)と呼ばれ、スタックは次のようになります：

--->getDepth(root.right) //this will return 0 immediately, and will be popped of the stack 
    getDepth(root) // this is your entry point 

再び、getDepth(root.right)が返されると、スタックからポップされ、呼び出しメソッドは実行を継続し、最後のifステートメントを実行します。

複数のノードを持つツリーに対して同じ実行パターンが適用されます。最終的には、再帰的なメソッド呼び出しが（例外がない限り）返され、呼び出し元のメソッドは次のステートメントから実行を継続します。