Exercise 5.29: Monitor the stack operations in
the tree-recursive Fibonacci computation:
(define (fib n)
(if ( n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
Give a formula in terms of n for the maximum depth of the stack required to
compute Fib
(
n
) for n
≥
2. Hint: In 1.2.2 we
argued that the space used by this process grows linearly with n.
Give a formula for the total number of pushes used to compute Fib
(
n
)
for n
≥
2. You should find that the number of pushes (which correlates
well with the time used) grows exponentially with n. Hint: Let
S
(
n
) be the number of pushes used in computing Fib
(
n
). You
should be able to argue that there is a formula that expresses S
(
n
) in
terms of S
(
n
−
1
), S
(
n
−
2
), and some fixed “overhead”
constant k that is independent of n. Give the formula, and say what
k is. Then show that S
(
n
) can be expressed as
a
⋅
Fib
(
n
+
1
)
+
b and give the values of a and b.
练习 5.29：监控树形递归 Fibonacci 计算中的栈操作：
(define (fib n)
(if ( n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
给出计算 n ≥ 2 的 Fib(n) 所需最大栈深度关于 n 的公式。提示：在 1.2.2 节中，我们论证了该计算过程所用空间随 n 线性增长。
给出计算 n ≥ 2 的 Fib(n) 所用总压栈次数的公式。你会发现，压栈次数（与所用时间密切相关）随 n 指数增长。提示：设 S(n) 为计算 Fib(n) 所用的压栈次数，你应能论证存在一个公式，用 S(n-1)、S(n-2) 及某个与 n 无关的固定“开销”常数 k 来表示 S(n)。给出该公式并说明 k 的值。然后证明 S(n) 可以表示为 a · Fib(n+1) + b，并给出 a 和 b 的值。
(define (fib n)
(if ( n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))