lisp フィボナッチ関数と二重再帰
よくあるLISPの例題にフィボナッチ数列の二重再帰の式があるのだけど、とりあえずトレースできていそうな手応えを得るまでに2週間も掛かった。あんまりわからないものだから色々手をつけているけど、これじゃあ死ぬまでにはとても終わりそうにないな。
解けるようになると何でもないのは根本的に解っていないせいだろう。
フィボナッチ数列の定義
最初のフィボナッチ数は1
次のフィボナッチ数も1
それ以降のフィボナッチ数は二つ前とひとつ前のフィボナッチ数を足して作ります。
1,1,2,3,5,8,13...
（リスト遊び p55 ss4.3 フィボナッチ数列、山本和彦 2000/06/01）
で、その例題は
M.HiroiさんのXyzzy LISP Programming の LIST7 フィボナッチ関数（再帰版）
(defun fibo (x)
(if (or (= 0 x) (= 1 x))
1
(+ (fibo (- x 1)) (fibo (- x 2)))))
fibo(x)に0から5を代入して上記の式を解く。
- (fibo(0)) = 1
- (fibo(1)) = 1
- (fibo(2)) = (+ (fibo(- 2 1)) (fibo(- 2 2))) = (+ (fibo(1)) (fibo(0))) = (+ 1 1) = 2
- (fibo(3)) = (+ (fibo(- 3 1)) (fibo(- 3 2))) = (+ (fibo(2)) (fibo(1))) = (+ 2 1) = 3
- (fibo(4)) = (+ (fibo(- 4 1)) (fibo(- 4 2))) = (+ (fibo(3)) (fibo(2))) = (+ 3 2) = 5
- (fibo(5)) = (+ (fibo(- 5 1)) (fibo(- 5 2))) = (+ (fibo(4)) (fibo(3))) = (+ 5 3) = 8
(fibo(x))を5で解くと
- (fibo(5)) = (+ (fibo(- 5 1)) (fibo(- 5 2))) = (+ (fibo(4)) (fibo(3)))
- 左から右へ展開して一回目の展開は完了。（上記のリスト６）
- この後(fibo(4))、(fibo(3))と展開は再帰呼び出しされて(fibo(0))まで進む。（５から１へ）
- するとカッコの殻を破って値が顔をだすので逆の順番で足し算が始まる。（１から６へ）
なんだか辻褄合わせで解けたような、それでいて理解はできていないような。ゆっくりでも進むしかない。
