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)))))

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 a Fib(n + 1) + b and give the values of a 
   and b.

————————————————————————————————————————————————————————————————————————

First we gather some data:

;;; EC-Eval input:
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(fib 2)
(total-pushes = 72 maximum-depth = 13)
1

(fib 3)
(total-pushes = 128 maximum-depth = 18)
2

(fib 4)
(total-pushes = 240 maximum-depth = 23)
3

(fib 5)
(total-pushes = 408 maximum-depth = 28)
5

(fib 6)
(total-pushes = 688 maximum-depth = 33)
8

(fib 7)
(total-pushes = 1136 maximum-depth = 38)
13

(fib 8)
(total-pushes = 1864 maximum-depth = 43)
21

(fib 9)
(total-pushes = 3040 maximum-depth = 48)
34

(fib 10)
(total-pushes = 4944 maximum-depth = 53)
55

(fib 11)
(total-pushes = 8024 maximum-depth = 58)
89

(fib 12)
(total-pushes = 13008 maximum-depth = 63)
144


The first few results:

    n    pushes    depth
    2    72        13
    3    128       18
    4    240       23
    5    408       28

The depth is clearly linear: max-depth = 5n + 3.

If S(n) is the stack pushes in (fib n) for n>1, then clearly this must 
be at least S(n-1) + S(n-2), since the procedure calculates these values 
recursively.

There is also some overhead k associated with setting up the recursive 
calls and adding the results.

Taking n=4 and substituting from the table of results above, we have:

S(4) = S(3) + S(2) + k
240  = 128  + 72   + k
k = 40

Therefore:

S(n) = S(n-1) + S(n-2) + 40

So for n=5:

S(5) = 240 + 128 + 40 = 408,

which is correct according to the results above.

The tree-recursive computation of the Fibonacci function builds up its 
answer only by means of recursive addition of 0 and 1.

It is easy to see that the returned result of the computation, then, 
will have required at least Fib(n) addition operations.

As a result we can easily prove that the asymptotic growth of the number 
of addition operations (and hence stack pushes) has the result as a 
lower bound.

The direct values take 16 pushes to return:

;;; EC-Eval input:
(fib 0)
(total-pushes = 16 maximum-depth = 8)
0

(fib 1)
(total-pushes = 16 maximum-depth = 8)
1

This means for n=0 or n=1 we have a constant cost of 16 pushes.
For n≥2, we have S(n) = S(n-1) + S(n-2) + k as shown above.

Therefore:

S(n) =  16                   if n=0 or n=1
     =  S(n-1) + S(n-2) + 40 otherwise

This is a Fibonacci-like sequence, starting with:

16,16,72,128,240,408,688,...

We can shift the Fibonacci function up to start with 1,1,2,... by adding 
one.  To account for the k=40 steps which are added repeatedly, we have 
to multiply by 16 + 40, then subtract the extra 40 at the end:

S(n) = 56 Fib(n+1) - 40

Here are the first few values, which match the experimental results:

    n    S(n)      Fib(n+1)
    0    16        1
    1    16        1
    2    72        2
    3    128       3
    4    240       5
    5    408       8
    6    688       13
    7    1136      21