SICP 問題 5.29
a: n≧2の時のfib(n)を計算するのに必要なスタックの最大深さのnを使った式を与えよ.
b: 同じ条件でfib(n)のプッシュの総数を求める
;;; EC-Eval input: (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (total-pushes = 3 maximum-depth = 3) ;;; EC-Eval value: ok ;;; EC-Eval input: (fib 0) (total-pushes = 16 maximum-depth = 8) ;;; EC-Eval value: 0 ;;; EC-Eval input: (fib 1) (total-pushes = 16 maximum-depth = 8) ;;; EC-Eval value: 1 ;;; EC-Eval input: (fib 2) (total-pushes = 72 maximum-depth = 13) ;;; EC-Eval value: 1 ;;; EC-Eval input: (fib 3) (total-pushes = 128 maximum-depth = 18) ;;; EC-Eval value: 2 ;;; EC-Eval input: (fib 4) (total-pushes = 240 maximum-depth = 23) ;;; EC-Eval value: 3 ;;; EC-Eval input: (fib 5) (total-pushes = 408 maximum-depth = 28) ;;; EC-Eval value: 5 ;;; EC-Eval input: (fib 6) (total-pushes = 688 maximum-depth = 33) ;;; EC-Eval value: 8 ;;; EC-Eval input: (fib 7) (total-pushes = 1136 maximum-depth = 38) ;;; EC-Eval value: 13 ;;; EC-Eval input: (fib 8) (total-pushes = 1864 maximum-depth = 43) ;;; EC-Eval value: 21 ;;; EC-Eval input: (fib 9) (total-pushes = 3040 maximum-depth = 48) ;;; EC-Eval value: 34 ;;; EC-Eval input: (fib 10) (total-pushes = 4944 maximum-depth = 53) ;;; EC-Eval value: 55
a: 最大深さは5n+3
b: プッシュ総数S(n)=S(n-1)+S(n-2)+40
オーバーヘッド定数kは40.