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

I find it very strange that we all have different a, b and K for fib, the max-depth formula is the same as cody's, while
S(n) = fib(n+1)*(S(1) + K) - K;
so a = S(1) + K
b = - K
also S(1) = S(0)
but my values differ from others
S(1) = 16
K = 40
S(n) = 56*fib(n+1) - 40
Also the order of growth is phi^(n+1) as fib(n+1) = (phi^(n+1) - (1 - phi)^(n+1))/sqrt(5)
which is equivalent to phi^n

;; a)
;; 
;; Fibonacci: Space: s(n)=3+8n, n>0; s(0)=11.
;; n = 0        pushes =   18   depth = 11      v = 0
;; n = 1        pushes =   18   depth = 11      v = 1
;; n = 2        pushes =   78   depth = 19      v = 1
;; n = 3        pushes =  138   depth = 27      v = 2
;; n = 4        pushes =  258   depth = 35      v = 3
;; n = 5        pushes =  438   depth = 43      v = 5
;; n = 6        pushes =  738   depth = 51      v = 8
;; n = 7        pushes = 1218   depth = 59      v = 13
;; n = 8        pushes = 1998   depth = 67      v = 21
;; n = 9        pushes = 3258   depth = 75      v = 34
;; n = 10       pushes = 5298   depth = 83      v = 55

;; b)
;;
;; S(n)=42+S(n-1)+S(n-2)
;; 
;; s(n) = k + s(n-1) + s(n-2)
;;
;; a = 18; k = 42
;;
;; s(0) =         a             =  18
;; s(1) =         a             =  18
;; s(2) =        2a     +   k   =  78
;; s(3) =        3a     +  2k   = 138
;; s(4) =        5a     +  4k   = 258
;; s(5) =        8a     +  7k   = 438
;; s(6) =       13a     + 12k   = 738
;;
;;  o
;;  o
;;  o
;;
;; s(n) = Fib(n+1) * a  + ( Fib(n+1) - 1 ) * k
;;
;; s(n) = 60 Fib(n+1) - 42