如何將遞歸函數轉換爲使用堆棧？

假設我有一棵樹使用深度優先搜索遍歷，而我遍歷它的算法看起來是這樣的：如何將遞歸函數轉換爲使用堆棧？

algorithm search(NODE): 
    doSomethingWith(NODE) 
    for each node CHILD connected to NODE: 
    search(CHILD)

現在，在許多語言中有一個最大深度遞歸，例如，如果遞歸的深度超過了一定的限制，那麼程序會因堆棧溢出而崩潰。

這個函數如何在沒有遞歸的情況下實現，而是使用堆棧？在很多情況下，有很多局部變量;他們在哪裏可以儲存？

來源

2010-08-02 Ran

我發現這個問題有一個無意的幽默元素，因爲大多數編程語言（儘管不是全部）會在內部使用堆棧。當然，還有一個事實是，對於大多數語言來說，通過深度優先搜索來達到遞歸限制要求您有一個非常不平衡的樹或非常非常大的樹，因爲您需要深度大約1000個和大多數平衡二叉樹的元素數量等於2^depth - 1，這意味着，對於那棵樹，在溢出之前需要2^1000-1個元素。 – JAB 2010-08-02 20:11:59

而且，當然，由於語言無論如何都可能使用堆棧來實現遞歸，所以導致遞歸形式溢出的問題也可能成爲顯式使用堆棧版本的問題。（雖然我不覺得這是一個糟糕的問題，但我現在只是感覺有些失落，並且心情很亂）。 – JAB 2010-08-02 20:14:26

事實上，我的樹非常非常大，雖然有一個大量相同的節點。因此，相同的節點被緩存在散列表中，但該樹仍然非常大。 – Ran 2010-08-02 20:19:30

你改變這一點，你會打擊你的堆使用堆棧像這樣：

algorithm search(NODE): 
    createStack() 
    addNodeToStack(NODE) 

    while(stackHasElements) 
     NODE = popNodeFromStack() 
     doSomethingWith(NODE) 
     for each node CHILD connected to NODE: 
     addNodeToStack(CHILD)

至於你的第二個問題：

在許多情況下，T這裏有很多局部變量;他們在哪裏可以儲存？

這些確實可以保留在原來的位置。如果變量是「doSomethingWith」方法的本地變量，只需將它們移入該變量，然後將其重構爲單獨的方法。該方法不需要處理遍歷，只需要處理，並且可以使用它自己的局部變量，這種方式僅適用於其範圍。

來源

2010-08-02 20:05:16

也許這很明顯，但是如果節點有本地狀態，除了本地處理變量，那麼你只需將它們添加到NODE的定義中即可。 – 2010-08-02 20:20:42

基本上你新的你自己的堆棧：或類型安全，node* in_process[] = new node*[1024];並把您對此的中間值：

node** current = &in_process[0]; 
node* root = getRoot(); 

recurse(root, &current) ;** 

void recurse(node* root, node** current) ; 
    *(*current)++ = root; add a node 
    for(child in root) { 
    recurse(child, current); 
    } 
    --*current; // decrement pointer, popping stack; 
}

來源

2010-08-02 20:02:27 tpdi

對於一個稍微不同的穿越。

push(root) 
while not empty: 
    node = pop 
    doSomethingWith node 
    for each node CHILD connected to NODE: 
     push(CHILD)

對於相同的遍歷按逆序推送節點。

如果你吹你的籌碼，這可能不會幫助，因爲不是

可避免推所有的孩子，如果你有一個nextChild功能

來源

2010-08-02 20:04:32 deinst

您通常會在堆棧之前以堆棧的方式堆棧堆棧內存大小通常限制在相當低的數量（即：1mb）。 – 2010-08-02 20:14:38

是的，但是如果你遞歸足夠的時間來吹走1M堆棧，你幾乎總是會做一些足夠錯誤的事情，以便輕鬆地吹掉另外3個數量級。 – deinst 2010-08-02 20:24:53

Eric Lippert創建了許多關於此主題的文章。例如看看這個： Recursion, Part Two: Unrolling a Recursive Function With an Explicit Stack

來源

2010-08-02 20:08:29 desco

如何將遞歸函數轉換爲使用堆棧？

回答

相關問題