不使用遞歸重寫遞歸函數

我正在重寫一些現有代碼，在遞歸調用不容易實現也不期望的設置中。（在Fortran 77中，如果你必須知道的話）。我曾經想過要從頭開始編寫一個堆棧以跟蹤所需的調用，但這看起來很糟糕，而且我寧願不在內存中分配內存遞歸不深。（我不相信Fortran 77支持動態數組大小調整。）不使用遞歸重寫遞歸函數

有關如何獲取明顯遞歸函數並在不浪費堆棧空間的情況下對其進行非遞歸重寫的一般解決方案的其他建議？

非常感謝，老MCST

來源

2010-12-12 Old McStopher

如果它不分支，通常可以將它重寫爲一個簡單的循環。如果它分支你通常需要一個堆棧 – CodesInChaos 2010-12-12 14:14:24

@CodeInChaos：一個不分支的遞歸函數，根據定義，永遠不會返回... – 2010-12-12 14:18:44

猜猜我濫用詞分支。我的意思是多次調用本身，所以調用的圖形變成了帶有分支的樹。這只是我的經歷，並不總是如此。 – CodesInChaos 2010-12-12 14:21:44

如果你的代碼使用尾遞歸（也就是說，該函數返回每個遞歸調用的結果直接，沒有任何其他處理），則有可能勢在必行重寫功能不會堆棧：

function dosomething(a,b,c,d) 
{ 
    // manipulate a,b,c,d 
    if (condition) 
    return dosomething(a,b,c,d) 
    else 
    return something; 
}

分爲：

function dosomething(a,b,c,d) 
{ 
    while (true) 
    { 
    // manipulate a,b,c,d 
    if (condition) continue; 
    else return something; 
    } 
}

沒有尾遞歸，使用棧（或類似的中間存儲）是唯一的解決方案。

來源

2010-12-12 14:17:42

這與我的想法類似，但無法用語言表達。因此，在我的具體情況中，我有一組數據元素，每個元素都需要測試與該集合中其他元素的關係。我可以傳入所有項目的數據結構，但由於每個項目都需要進一步處理，所以我認爲堆棧是不可避免的，是的？ – 2010-12-12 14:30:45

取決於。如果代碼主要是「對於所有對（a，b），如果P（a，b）是真的，那麼執行F（a，b）」，你可以通過迭代循環遍歷所有的對... – 2010-12-12 14:39:58

大多數遞歸函數可以很容易地改寫爲圈，以浪費空間 - 這取決於功能，因爲許多（但不是全部）遞歸算法實際上是依賴於那種存儲（儘管在這些情況下循環版本通常也更有效）。

來源

2010-12-12 14:15:59 Ofir

小心顯示一個不需要堆棧空間的遞歸函數？即使它的論點？ – 2010-12-12 14:28:35

@Nikita Rybak：內聯尾遞歸函數;） – 2010-12-12 14:37:49

@Victor是的，但這是在改寫的形式。 Ofir聲稱有一個不需要堆棧內存的遞歸函數。所以，我很好奇。 – 2010-12-12 15:10:06

可以寫成循環經典遞歸函數是斐波那契數函數：

function fib(n) 
{ 
    // valid for n >= 0 
    if (n < 2) 
     return n; 
    else 
     return fib(n-1) + fib(n-2); 
}

但是，如果沒有記憶化這需要O（EXP^N）與O操作（N）堆棧空間。

可以改寫：

function fib(n) 
{ 
    if (n < 2) 
     return n; 
    var a = 0, b = 1; 
    while (n > 1) 
    { 
     var tmp = a; 
     a = b; 
     b = b + tmp; 
     n = n - 1; 
    } 
    return b; 
}

但是，這涉及到的功能是如何工作的，不知道這是否可以推廣到一個自動的過程知識。

來源

2010-12-12 16:51:54

不使用遞歸重寫遞歸函數

回答

相關問題