树递归斐波那契算法需要线性空间？

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

正常顺序评估与应用顺序评估之间的差异类似于深度优先搜索算法与宽度优先搜索算法算法之间的差异。

在这个原因中，它是一个正常顺序评估，作为参数的所有组合将被逐个评估，直到没有组合从左到右的顺序（当组合正在评估时，如果存在仍然是组合内的组合进行评估，这些组合中的第一个将在下一次评估之后立即进行评估，并继续这样下去），这意味着当第一组合得到时，空间将首先扩大然后缩小评估。

继续像这样，第二，第三。为整个评估做出最大空间取决于评估流程的深度。

因此树递归斐波那契算法需要线性空间。它会帮助