我知道斐波那契级数呈指数增长，因此递归算法具有所需的指数增长步数，但是 SICP v2 说树递归斐波那契算法需要线性空间，因为我们只需要跟踪树中我们上方的节点。
我知道所需的步数与 Fib(n( 呈线性增长，但我也假设由于树呈指数级扩展，因此此事件中所需的内存也需要呈指数增长。有人可以解释为什么所需的内存仅线性扩展到N，而不是指数扩展吗？
我猜这是在评估中使用应用顺序的结果。鉴于
(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中盯着这句话的时间比我愿意承认的要长之后的答案。
您不存储整个树，而只存储与您当前深度一样多的堆栈帧。
正
态阶求值和应用阶求值之间的差异类似于深度优先搜索算法和广度优先搜索算法算法之间的差异。
在这个原因中，它是一个正态顺序评估，所有作为参数的组合将被逐个评估，直到不再有从左到右的顺序的组合(当组合正在评估时，如果正在评估的组合内部仍有组合，这些组合中的第一个将在下一次评估中立即评估， 然后继续这样下去。这意味着当第一个组合得到评估时，空间将首先扩大，然后缩小。
然后继续这样下去，第二个，第三个。使整个评估的最大空间取决于评估过程的深度。
因此，树递归斐波那契算法需要线性空间。