樹遞歸斐波那契算法需要線性空間？

Question

我知道斐波納契數列按指數規律增長，因此遞歸算法具有按指數規律增長的所需步數，但SICP v2表示樹遞歸斐波那契算法需要線性空間，因爲我們只需跟蹤我們上方的節點在樹上。

據我所知，所需要的步數增長線性與纖維蛋白原（N），但我也認爲，因爲樹是成倍擴大，在這種情況下所需的內存將需要指數爲好。有人可以解釋爲什麼所需的內存只能線性擴展到N，而不是指數級擴展？

Answer 1

你不存儲整個樹，但只有儘可能多的堆棧幀作爲是當前深入你在。

Answer 2

我猜這是評價使用應用性秩序的結果。鑑於

(define (fib n) 
(cond ((= n 0) 0) ((= n 1) 1) (else (+ fib (- n 1)) (fib (- n 2)))))) 

[從計算機程序的結構和解釋]

正常秩序評價（FIB 5）將不斷擴大，直到它得到原始表達式：

(+ (+ (+ (+ (fib 1) (fib 0)) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0) (fib 0))) 

那會導致樹的所有葉子被存儲在內存中，這將需要與n指數相關的空間。

但是應用順序評估應該不同地進行，沿着一個分支向下驅動到兩個葉，然後升高分支並累積任何側分支。這將導致（fib 5）的最大長度表達式爲：

(+ (+ (+ (+ (fib 1) (fib 0)) (fib 1)) (fib 2)) (fib 3)) 

該表達式比在正常順序評估中使用的表達式短得多。該表達式的長度不受樹中樹葉數量的影響，僅受樹的深度影響。

這是我在SICP上看到這句話後的回答，我有更多的時間比我關心的承認。

Answer 3

正常順序評估與應用順序評估之間的差異類似於深度優先搜索算法與寬度優先搜索算法算法之間的差異。

在這個原因中，它是一個正常順序評估，作爲參數的所有組合將被逐個評估，直到沒有組合從左到右的順序（當組合正在評估時，如果存在仍然是組合內的組合進行評估，這些組合中的第一個將在下一次評估之後立即進行評估，並繼續這樣下去），這意味着當第一組合得到時，空間將首先擴大然後縮小評估。

繼續像這樣，第二，第三。爲整個評估做出最大空間取決於評估流程的深度。

因此樹遞歸斐波那契算法需要線性空間。它會幫助