ツリー関数の再帰コードですか？

Question

Iは、ツリーの最初のノードを返す機能を有するが、

node* primeiro(tree r){ 
    while(r->left != NULL){ 
     r = r->left; 
    } 
    return r; 
} 

ところで、PERCUSSが順に行われます。したがって、関数はツリーの一番左の葉を返し、関数はツリーが空でないと推定します。どのように再帰的な方法でこれを実装できますか？

node* primeiro (tree r) { 
    while (r->left != NULL) { 
    r = primeiro (r->left); 
    } 
    return r; 
} 

これは機能しません。

Answer 1

問題はwhileを使用していることです。単純なrecursion termination conditionが必要です。

node* primeiro (tree r) { 
    if (r->left != NULL) { 
     r = primeiro (r->left); 
    } 
    return r; 
} 

Answer 2

の代わりにwhileループの条件R->左！= NULLを使用して、真または偽のためにそれを確認してください。 （これは再帰終了の基本条件となります）。あなたの機能の私たちは、「再帰関数」について語るとき、私たちは通常、「ループに再帰を使用する関数」を意味

Answer 3

...

の両方がループにwhileを使用しています。そのwhileループを再帰関数呼び出しに変換することに焦点を当てる必要があります。これにそれを変換

int fubar(int x) { 
    while (x > 0) { 
     x--; 
    } 
    return x; 
} 

：：2がどの程度似ているかを

int fubar(int x) { 
    if (x > 0) { 
     return fubar(x - 1); 
    } 
    return x; 
} 

お知らせ

は、このループを考えてみましょう。違いは次のとおりです。

• 再度x直接ではなくあなたのループテストがif声明、ないwhileである
• にxの異なる値を渡すことで...
• を変更している、あなたは」ループを繰り返さずにwhileを使用します。代わりにfubarを呼び出して、新しい値を渡してその結果を返す必要があります。

重要な注：すべての再帰関数呼び出しの直後にリターン（中間計算は必要ありません）が確実に行われるように、significant benefitsが存在する可能性があります。

Answer 4

反復が再帰に置き換えられているとき、無限再帰ループで始まることで、右のコードを導出する方が簡単かもしれ：

node* primeiro(tree r){ 
    /* What goes in the recursive loop body? */ 
    return primeiro(r); 
} 

あなたは今何反復の次の値が希望の下で求めることができ、いつループが停止しますか？次の価値はかなりまっすぐです。 whileループロジックから

node* primeiro(tree r){ 
    /* When does the recursive loop stop? */ 
    r = r->left; 
    return primeiro(r); 
} 

r->leftがNULLあるとき、ループが停止します。その時点で、rを返します。

node* primeiro(tree r){ 
    if (r->left == NULL) return r; 
    r = r->left; 
    return primeiro(r); 
}