理系学生日記

おまえはいつまで学生気分なのか

問題 3-57 (3.5.2 Infinite Streams)

以下のように定義されたフィボナッチ数列 fibs について,第 n 項を計算するのに必要な加算回数はどう増えていくでしょうという問題.ただしメモ化はなし.

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

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

最初の要素は 0 で,このときの計算回数は 0 です.
次の要素は 1 で,このときの計算回数は 0 です.
3 番目の要素を取り出そうとすると,0 + 1 が行われるので,計算回数は 1.
4 番目の要素を取り出そうとすると,まず 2 番目の要素を計算するために 0 回,そして3 番目の要素を計算するために 1 回計算が必要ですから,計算回数は 1.
5 番目の要素を取り出そうとすると,まず 3 番目の要素を計算するために 1 回,そして4 番目の要素を計算するために 1 回計算が必要ですから,計算回数は 2.
なんだかフィボナッチ数列と同じ感じで計算回数が増えていくのがわかります.まぁそれで指数的に増えていくってのはなんとなくわかりますね.