読者です 読者をやめる 読者になる 読者になる

阿房峠

tunaguinfoのブログ

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を代入して上記の式を解く。

  1. (fibo(0)) = 1
  2. (fibo(1)) = 1
  3. (fibo(2)) = (+ (fibo(- 2 1)) (fibo(- 2 2))) = (+ (fibo(1)) (fibo(0))) = (+ 1 1) = 2
  4. (fibo(3)) = (+ (fibo(- 3 1)) (fibo(- 3 2))) = (+ (fibo(2)) (fibo(1))) = (+ 2 1) = 3
  5. (fibo(4)) = (+ (fibo(- 4 1)) (fibo(- 4 2))) = (+ (fibo(3)) (fibo(2))) = (+ 3 2) = 5
  6. (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)))
  • 左から右へ展開して一回目の展開は完了。(上記のリスト6)
  • この後(fibo(4))、(fibo(3))と展開は再帰呼び出しされて(fibo(0))まで進む。(5から1へ)
  • するとカッコの殻を破って値が顔をだすので逆の順番で足し算が始まる。(1から6へ)

なんだか辻褄合わせで解けたような、それでいて理解はできていないような。ゆっくりでも進むしかない。