sicp-ex-5.29

  
  
 (a) 
 n   total-pushes    maximum-pushes 
 1         18                       11 
 2         78                       19 
 3        138                      27 
 4        258                      35 
 5        438                      43 
 the maximu-pushes is: 8n + 3 
 (b) 
 S(n) = S(n-1) + S(n-2) + 42 
 S(n) = 60Fib(n+1) - 42 

Results
=======

┌────┬───────────┬───────────────┬──────────────────┐
│  n │ Fibonacci │ Maximum Depth │ Number of Pushes │
├────┼───────────┼───────────────┼──────────────────┤
│  1 │      1    │        8      │          22      │
├────┼───────────┼───────────────┼──────────────────┤
│  2 │      1    │       13      │          78      │
├────┼───────────┼───────────────┼──────────────────┤
│  3 │      2    │       18      │         134      │
├────┼───────────┼───────────────┼──────────────────┤
│  4 │      3    │       23      │         246      │
├────┼───────────┼───────────────┼──────────────────┤
│  5 │      5    │       28      │         414      │
├────┼───────────┼───────────────┼──────────────────┤
│  6 │      8    │       33      │         694      │
├────┼───────────┼───────────────┼──────────────────┤
│  7 │     13    │       38      │       1,142      │
├────┼───────────┼───────────────┼──────────────────┤
│  8 │     21    │       43      │       1,870      │
├────┼───────────┼───────────────┼──────────────────┤
│  9 │     34    │       48      │       3,046      │
├────┼───────────┼───────────────┼──────────────────┤
│ 10 │     55    │       53      │       4,950      │
├────┼───────────┼───────────────┼──────────────────┤
│ 11 │     89    │       58      │       8,030      │
└────┴───────────┴───────────────┴──────────────────┘


Part A
======

  Max pushes = 5n + 3


Part B
======

Formula for Number of Pushes wrt previous values:

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

Formula for Number of Pushes wrt next Fibonacci number:

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


Calculation:
============

  S(2):  78 = a.2 + b
  S(3): 134 = a.3 + b

  S(3) - S(2):
    (134 - 78) = (3a + b) - (2b + b)
          56 = (3a - 2a) + (b - b)
           a = 56

  S(2):  78 = a.2 + b
         78 = (56 * 2) + b
   78 - 112 = b 
          b = -34


Without Tail Recursion:
=======================

Without tail recursion I got results more closely matching meteorgan's  
results:

  Max pushes = 8n + 6

  S(n) = 60 Fib(n+1) + -34