我知道斐波那契数列呈指数增长,因此递归算法所需的步数呈指数增长,但是 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 中盯着那句话看了比我愿意承认的时间更长的时间后的答案。
关于algorithm - 树递归斐波那契算法需要线性空间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27345652/