如何將遞歸函數模型模擬爲帶有堆棧的迭代函數模型？

我們來考慮一下從其中序遍歷和後序遍歷構造二叉搜索樹的問題。現在在遞歸實現中，我會這樣做：如何將遞歸函數模型模擬爲帶有堆棧的迭代函數模型？

node.left = recursive（start，mid-1）; node.right =遞歸（mid + 1，end）;

現在我將如何去實現這與堆棧？一旦從堆棧彈出一個節點，我就不能回到它。這種迭代方法僅適用於遍歷嗎？

這是整個代碼，其中_constructInPost是遞歸的要點：

Node<T> _constructInPost (List<T> in, List<T> post) { 

    if (in.size() == 0) 
     return null; 

    Node<T> root = new Node <T>(post.get(post.size()-1)); 

    int index = 0; 
    for (; index < post.size(); index++) { 
     if (in.get(index) == root.data) 
      break; 
    } 

    root.left = _constructInPost (in.subList(0, index), post.subList(0, index)); 
    root.right = _constructInPost (in.subList(index+1, in.size()), post.subList(index, post.size()-1)); 

    return root; 
}

來源

2014-09-11 shrinidhisondur

可以隨時替補遞歸與迭代，因爲這是操作系統做背景，你的整個代碼是什麼？ – 2014-09-11 05:32:52

我編輯了描述。 – shrinidhisondur 2014-09-11 05:36:30

答案是，「學習等等。」 :-)

您的堆棧將包含有關如何操作的說明。所以如果你想要2次遞歸調用，你將在堆棧中放置2個命令。如果你有工作要做，你會做這件事。如果你想做2次遞歸調用，然後結果是其他東西，你需要在你的棧指令上放置其他的東西，然後遞歸調用。（這樣，你沒有得到其他的東西，直到遞歸發生後），那麼你的基本循環具有以下模式：

while stack.length(): 
    command = stack.pop() 
    if command.name == 'recursive_call': 
     do recursive code that may add to the stack 
    elif command.name == 'base case': 
     do base case

來源

2014-09-11 05:53:00 btilly

所以我最好做一個遞歸然後，因爲實際上我們在這裏實現一個函數堆棧。我對嗎？ – shrinidhisondur 2014-09-11 06:04:27

@shrinidhisondur是的，這就是從遞歸到迭代實現工作方式的變化，一般情況下，你要做什麼操作系統會爲你做什麼（創建函數調用堆棧，有些情況下你可以節省一些內存/時間） – 2014-09-11 06:27:28

在實踐中，你遞歸最好。但你最好還是理解這種方法。因爲如果你只理解遞歸，將深度優先搜索轉換爲寬度優先搜索的簡單挑戰是不可能的。如果你理解了這種方法，那麼你可以說，「用一個隊列替換一個堆棧」，你就是這個方法的最大的一部分。 – btilly 2014-09-11 06:29:42

如何將遞歸函數模型模擬爲帶有堆棧的迭代函數模型？

回答

相關問題