# 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` .