The stack operations in the tree-recursive Fibonacci computation
Monitor the stack operations in the tree-recursive Fibonacci computation:
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
a. Give a formula in terms of
n
for the maximum depth of the stack required to compute
Fib(n)
for
n ≥ 2
. Hint: In section 1.2.2 we argued that the space used by this process grows linearly with
n
.
b. 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
aFib(n + 1) + b
and give the values of
a
and
b
.