0

関数の再帰が理解できません。使い方？値はどのように保存されますか?

int tree_size(struct node* node) { 
  if (node==NULL) {
    return(0); 
  } else { 
    return(tree_size(node->left) + tree_size(node->right) + 1); 
  } 
}
4

4 に答える 4

2

関数に入ると、新しいスタック フレームが (メモリ内のスタック上に) 作成されます。スタック フレームは、ローカルで定義された変数や入力引数など、その関数内のローカル データを追跡します。(そして、リターンアドレスや以前に保存されたレジスタ値など、保存する必要があるものもあります。ただし、これはこの質問には関係ありません。)

再帰を使用して、同じ関数内から関数を呼び出すと、(他の呼び出しと同様に) 新しいスタック フレームが作成され、その新しいスタック フレームに新しい呼び出しのローカル変数が格納されます。

C. Stoll が指摘したように、+ 演算子のため、2 つの呼び出しの順序は指定されていません。

于 2012-07-26T08:23:50.260 に答える
0

次の3つを検討してください

     1
  2 3
 4 5 6
7

1 には 2 つの子 (2 と 3) があり、2 には 2 つの子 (4 と 5) があります。4 には 1 つの子 (7)
があり、1 でのツリーのサイズを知りたい場合:

tree_size(tree1);

tree1 は NULL ではないため、if 条件が true ではないため、else ステートメントが実行されます。

tree_size(tree1): return tree_size( tree_size(tree2) + tree_size(tree3) + 1 )

tree2 と tree3 も同様

tree_size(tree2): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 )
tree_size(tree3): return tree_size( tree_size(tree6) + tree_size(NULL) + 1 )

等々。ここで、tree_size(tree2) と tree_size(tree3) の戻り値を tree_size(tree1) に代入すると、次のようになります。

tree_size(tree1): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 + tree_size(tree6) + tree_size(NULL) + 1 + 1 )

これで、1+1+1 という用語が表示されます。これは、最初の 2 つのニボーのツリーのサイズです。tree_size 呼び出しを代用し続けると、n が木

于 2012-07-26T08:38:08.633 に答える
0

紙を使用することとの類似性 (Q へのコメントの @nhahtdh による) は非常に優れています。詳しく説明しましょう。

まず、コードをより直線的な方法で書き直します。

int tree_size(struct node* node) { 
  if (node==NULL) {
    return(0); 
  } else { 
    x = tree_size(node->left);
    y = tree_size(node->right);
    z = x + y;
    r = z + 1;
    return( r ); 
  } 
}

目の前に空の紙の厚い (事実上無尽蔵の) スタックがあると想像してください。また、デスクの左側にはさまざまなレシピ (関数定義) があり、右側には空のスペースがあります。

ここで、関数を呼び出すとは、その定義をレシピから目の前の紙の束の上にある紙にコピーし、呼び出しの引数値を関数パラメーターに置き換えて、そこから先に進むことを意味します。

関数呼び出し(任意の関数呼び出し)のある行にヒットしたら、目の前の紙にその行をマークし、その紙を右に移動して (上向きに)、新しい空のシートで作業を開始します。目の前の紙。呼び出す必要がある関数のレシピをコピーし、引数の値を書き留めて、目の前のレシピに従って作業を続けます。

別の関数呼び出しが発生した場合は、この一連のアクションを繰り返します。関数呼び出しの結果を受け取る必要がある行をマークし、現在の紙を右側の山の上に (上向きに) 置き、新しいレシピを上にコピーします。目の前に一番上の紙を置き、そこから前と同じように進みます。

現在のレシピで という行にヒットしたらreturn、返された値を一番上の紙の山に書き留めて、そこのマークされた行の右側に置き、次に目の前の現在の紙を捨てて後ろに移動します。紙の束の一番上の紙をあなたの目の前の紙の束の上に置きます。

それでおしまい。必要なのは、前と右に 1 枚の 2 枚の紙の山と、左に関数の定義が書かれた紙の山だけでした。

呼び出す関数が、以前に実行した関数呼び出しのいずれかと同じであるかどうかは気にしないことに注意してください。それはまったく同じように機能します。

于 2012-07-26T09:54:52.693 に答える
0

あなたを最も混乱させている行は..

return(tree_size(node->left) + tree_size(node->right) + 1);

最上位のノードでこの関数を呼び出した場合、ツリー内のノードの数は、左側のノードの数と右側のノードの数と、関数を呼び出したばかりのノードのこれを足したものであることがわかります。

さて、あなたを混乱させているのは再帰ではないと思います。もしそうなら、コメントを残してください。もう少し説明できます。

あなたが抱えている問題は、行が実行される順序です。まあ、それは「足し算」の論理的な数学の規則に従います。tree_sizeを返す場合のように、演算子のオーバーロードを気にする必要がないことはわかっているintので、

intA + intB + intC;

これら 3 つの値をどの順序で追加しても、同じ結果が得られることは言うまでもありません。

ただし、これらが追加される順序は明確に定義されています。演算子を機能と考えると+、少し明確になります。基本的には次のとおりです (これが正しく行われることを願っています)。

operator+(intA , operator+( intB, intC);

ご覧のとおり、A を加算する前に、まず B + C を計算する必要があります。または、これを問題のコード行に戻すと、tree_size最初に右側を取得し、それに 1 を加算してから加算します。左側tree_sizeにあります。これは注意すべき重要なことです。値を取得するときにツリーのサイズを編集するなど、非常に奇妙なことを行うことができます...たとえば、ノードを一方の側から他方の側に移動した場合などです。もちろん、サイズを取得することが信頼できるものではない場合、それは非常に悪いツリーになります。

ここで少しやりすぎたのではないかと心配しているので、マークを少し逃した場合は、コメントを残してください。この回答を改善するために喜んでお手伝いします.

于 2012-07-26T08:57:47.800 に答える