我不完全理解這些遞歸調用何時返回

Question

我理解簡單的遞歸代碼，但有時會變得有點複雜。我迷路了，不能真正遵循代碼。 例如後續代碼（匿名寫的）：

void reversetree(struct node* head) 
{ 
//first check for the exception whether does it even exit or not 
if(head==NULL) 
return ; 

reversetree(head->left); //reverse call for left child 
reversetree(head->right); //same reverse call for right child 

//now next these steps will swap the children 
struct node* temp=head->left; 
head->left=head->right; 
head->right=head->left; 
//now exit the function and you are done :) 
} 

     6 
    / \ 
    3  4 
    /\ /\ 
    1 2 8 9 

比方說，如果二進制樹是這個樣子，有人可以做到一步步邏輯我好嗎？爲了我的理解，它首先檢查是否存在根，如果它存在，那麼它會再次調用左側子項的函數，直到沒有更多的左側子項爲止。所以當交換它的代碼被調用時呢？什麼時候開始用正確的孩子調用函數？對不起，我不太注意遞歸。

Answer 1

如果根不存在，則函數退出，因爲它沒有子項。

是，則處理器會按照他留下了孩子的鏈，直到耗盡，那麼最後一個節點的右孩子的留守兒童...

對於樹，這裏顯示的會發生什麼：

Reverse node 6: 
    Reverse node 3: 
    Reverse node 1: 
     Reverse NULL 
     Reverse NULL 
     Swap 1's links to NULL and NULL 
    Reverse node 2: 
     Reverse NULL 
     Reverse NULL 
     Swap 2's links to NULL and NULL 
    Swap 3's links to 1 and 2 
    Reverse node 4: 
    Reverse node 8: 
     Reverse NULL 
     Reverse NULL 
     Swap 8's links to NULL and NULL 
    Reverse node 9: 
     Reverse NULL 
     Reverse NULL 
     Swap 9's links to NULL and NULL 
    Swap 4's links to 8 and 9 
    Swap 6's links to 3 and 4 

它會運行得更快，在之前的NULL 之前進行測試。

交換步驟可以在遞歸調用之前進行，而不會影響速度或結果。

Answer 2

通常在處理遞歸時，人們傾向於告訴你用筆和紙做。它是一種偉大的運動，但我覺得更容易做這些方式：

第一種方式來看待它

有使用遞歸函數和執行不同的功能沒有什麼區別同樣的工作。他們都做他們的工作並返回，以便您的代碼在下一行繼續。

假設你有一個反轉一整棵樹工作功能，reversetree_external這樣你就可以這樣寫你的功能，無需遞歸：

void reversetree(struct node* head) 
{ 
    if(head==NULL) 
     return ; 

    // switch left and right 
    struct node* temp=head->left; 
    head->left=head->right; 
    head->right=temp; // There was an error here 

    // Reverse subtrees 
    reversetree_external(head->left); 
    reversetree_external(head->right); 
} 

的是，給予所以你需要說服自己一切參數，如：

 6 
    / \ 
    3  4 
    /\ /\ 
    1 2 8 9 

假作reversetree_external之前以下顛倒了兩個子樹：

 6 
    / \ 
    4  3 
    /\ /\ 
    8 9 1 2 

如果你只通過的right一個left它將把該級別使用reversetree_external不要做任何事情之前。

如果你通過它的葉節點，例如。 8結果是相同的8（與空指針交換）和reversetree_external將不會做任何事情，因爲它會被給予NULL兩次。

事實上，您可以看到reversetree可以做與reversetree_external相同的事情，因此您可以使用reversetree本身而不是依賴它。

二的方式來看待它

現在，這是很好的看這兩種方式，從而做到在倒車時，如。從NULL開始..例如。 8的左節點，然後是葉子，然後是使用樹葉的樹，然後是使用我們預先計算的子樹的完整樹。

input    result 
NULL    NULL 

8     8 

9     9 

1     1 

2     2 

    4    4 
/\   /\ 
8 9   9 8 

    3    3 
/\   /\ 
1 2   2 1 

    6    6 
/ \  / \ 
    3  4  4  3 
/\ /\ /\ /\ 
1 2 8 9 9 8 2 1 

因此，我只是在結果中使用以前的結果，你知道相同的功能會做。例如。我按照程序使用的方式切換3和4，這兩個遞歸就像之前完成的子樹一樣。

第一種方法是如何讀取遞歸代碼，第二種方法可能是最簡單的，以及如何輕鬆地創建自己的遞歸函數。您從基本案例開始並測試它們，然後添加一個默認情況下如何處理稍微複雜的問題，將其轉化爲更小的類似問題，最終成爲基本案例。