樹函數的遞歸代碼？

Question

我有一個返回樹的第一個節點的功能，

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

順便說一句，在叩診是爲了做。所以函數返回樹的最左邊的葉，函數假定樹不是空的。我怎樣才能以遞歸的方式實現這個？

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

而不是使用條件的R->離開！= NULL爲while循環，檢查其是否真的還是假的。 （這將是遞歸終止的基本條件）。

Answer 3

當我們談到「遞歸函數」，通常是指「使用遞歸循環功能」 ......

您的兩個功能是使用while循環。您應該專注於將該循環轉換爲遞歸函數調用。

考慮這個循環：

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

它轉變成這樣：

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

注意到兩者的相似程度。區別是：

• 你改變x並不直接，但在
• 你的循環試驗合格的x不同的值處於if聲明，不while ...
• 再次，你」不使用while循環;相反，您應該再次撥打fubar，傳入一個新值並返回結果。

重要注意事項：可能有significant benefits以確保每個遞歸函數調用後立即返回（不需要任何中間計算）。

Answer 4

當迭代被遞歸更換，可能會更容易通過與無限遞歸循環開始推導出正確的代碼：

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

現在，您可以在問什麼會迭代的下一個值，循環何時停止。下一個值非常簡單。

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

從while環路邏輯，當r->left是NULL循環停止。此時，您將返回r。

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