當下面的程序有2個遞歸語句時，如何執行遞歸？

我之前發佈過一個問題，但我並不清楚。我的混亂很抱歉，但如果有一個項目像什麼，我的意思是：當下面的程序有2個遞歸語句時，如何執行遞歸？

TreeNode createMinBST(int arr[], int start, int end) { 
    if(end< start) return null; 

    int mid = (start+end)/2; 
    Treenode n= new Treenode(arr[mid]); 
    n.left= createMinBST(arr, start, mid-1) //LINE a 
    n.right= createMinBST(arr, mid+1, end); //LINE b 
    return n; 
}

如何LINE和B線UNROLL或者它是如何工作（就像在編碼採訪書中說）？ LINE a是否一直到基本情況並返回值，然後LINE b執行？或者這兩個遞歸語句同時歸結爲基本情況？

如果有人能解釋水平明智的路徑創建從上面的代碼中的最小BST，這將是真正有助於瞭解如何遞歸多個語句（這裏2-線和B線）發生

謝謝很多

來源

2012-01-07 user807496

爲什麼不直接按照程序流程手動？或者通過在調試器中逐步觀察真實情況。 – 2012-01-07 17:50:31

[多遞歸展開]的可能重複（http://stackoverflow.com/questions/8770492/multiple-recursion-unrolling） – Mat 2012-01-07 17:51:01

@ Mat-我在這裏再次發佈它，因爲我的問題因爲不夠清晰而關閉。 – user807496 2012-01-07 17:51:55

看着你的代碼，你正在構建你的樹，就像你做「深度優先搜索」一樣。所以你要深入瞭解（在你的案例中留下），直到沒有更多的元素可以處理，然後你又回到了一個層次，然後再回落。

（順便說一句你的「A線」缺少在最後一個分號）

正如人們經常學習或試圖找出如何遞歸調用工作時的情況下，可以很方便地打印打出電話。

例如，在你的情況下，如果你的出發數組包含[10..24]那麼您的通話可能看起來像這樣的數字：

Calling minBST on 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 

    Calling minBST (left) on 10, 11, 12, 13, 14, 15, 16 

     Calling minBST (left) on 10, 11, 12 

      Calling minBST (left) on 10 

      Calling minBST (right) on 12 

     Calling minBST (right) on 14, 15, 16 

      Calling minBST (left) on 14 

      Calling minBST (right) on 16 

    Calling minBST (right) on 18, 19, 20, 21, 22, 23, 24 

     Calling minBST (left) on 18, 19, 20 

      Calling minBST (left) on 18 

      Calling minBST (right) on 20 

     Calling minBST (right) on 22, 23, 24 

      Calling minBST (left) on 22 

      Calling minBST (right) on 24

來源

2012-01-07 19:13:50 TacticalCoder

良好的分析...現在獎勵你自己一個漂亮的SO顯示名稱:) – Paul 2012-01-07 20:04:53

@保羅：嗯，我會盡快做到這一點:) – TacticalCoder 2012-01-07 20:16:10

該代碼按順序執行。

因此，第一次n.left被命中，它必須在下一行執行之前執行該語句。這意味着是的，它「保存」它的位置並從n.left一直沿着遞歸樹行進，然後它有完成行n.left行然後可以繼續執行（到n.right）。

來源

2012-01-07 17:52:14

user9889052做了很好的跟蹤。更簡單的答案是從上到下。直到返回頂級遞歸（在每個級別），下面的遞歸將不會被執行。

按照慣例我會說左邊總是最上面的語句。

事實上，遞歸無非就是一棵樹。

      Root 
        /     \ 
        RecurA    RecurB 
      /  \ 
     RecurAa  RecurAb 
     / \ 
     RAaa RAaab 
    / \ 
    dead dead

編輯當達到死（返回），它進入到右邊，直到同一級別的所有節點都「死」（返回所有的遞歸語句），它進入返回一級，並展開RAaab。

旁邊的問題：你能猜出這棵樹的深度嗎？這變得很明顯，爲什麼如果子問題是不好的，遞歸會是有問題的。

遞歸在每次調用（每個級別調用）後都會生成一個堆棧幀。上一級的信息是「存儲」的。當你開始彈出（當你點擊返回語句時向後移動），爲上一級保存的信息現在恢復。這個機制比這個簡單的描述複雜得多。

MinBST起初可能不是個好主意。改爲嘗試這種遞歸。

Given an array [3,4,9,2,0,11,8,-1,2,4] 
Partition this array in halves until size of each partition is one 
Then give the sum of the left and right partition as they return (at each level)

來源

2012-01-07 19:54:58 CppLearner

當下面的程序有2個遞歸語句時，如何執行遞歸？

回答

相關問題