SICP問題3.57

add-sstreams 手続き fibs の定義を使い, n番目の Fibonacci 数を計算する時、加算は何回実行されるか?
memo-proc が用意する最適化を行わずに(delay )を単に(lambda () )と実装したとすると、加算の回数が指数的に大きくなることを示せという問題。

add-streams (教科書で定義)

(define (add-streams s1 s2)
  (stream-map + s1 s2))

これを以下のように変更して加算回数をデバッグできるようにする

(define (fib-debug-add x y)
  (display "+")
  (+ x y))
(define (add-streams s1 s2)
;  (stream-map + s1 s2))
  (stream-map fib-debug-add s1 s2))

add-streams を使用した fibs手続き(教科書で定義)

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

実験
memo化版の場合、順番にやってくと新規の加算のみが実行されて常に計算+が一回しか表示されないので、n=10, n=20でやってみる

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))
; fib
(stream-ref fibs 20)
; +++++++++++++++++++6765
(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))
; fib
; => 19回
(stream-ref fibs 10)
; +++++++++55
; 9回

非メモ化版の場合

(stream-ref fibs 2)
; +1
; => 1回
(stream-ref fibs 3)
; +++2
; => 3回
(stream-ref fibs 4)
; +++++++3
; => 7回
(stream-ref fibs 5)
; ++++++++++++++5
; => 14回
(stream-ref fibs 6)
; ++++++++++++++++++++++++++8
; => 26回
(stream-ref fibs 7)
; ++++++++++++++++++++++++++++++++++++++++++++++13
; => 46回
(stream-ref fibs 8)
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++21
; => 79回
(stream-ref fibs 9)
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++34
; => 133回
(stream-ref fibs 10)
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++55
; => 221回

という感じで指数的に増えていく