フィボナッチ

SICP開催に向けての復習をしてる
少し触ってないと本当にいろいろと忘れてしまっていて怖い(((>＿<)))
折角習得したTeXもまた復習し直しですよ・・・
まずはフィボナッチの漸化式

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  (n≧2)

でもこれってユークリットの互除法だったんですね！
ユークリットの互除法とは2つの最大公約数を求める手法です

2個の整数a,b(a≧b)があったとき aをbで割った時の余りがrの時に
aとbの最大公約数はbとrの最大公約数に等しい
この性質を利用して
　　　aをbで割った時の余りをr  　bをrで割った時の余りをs
とした場合r割るsを繰り返した時の値が0になった時の除数がaとbとの最大公約数となる

最古のアルゴリズムですね
id:hogelogさんから過去に教えて頂いたユークリッドの互除法のアルゴリズムはコレ

1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、 m を出力してアルゴリズムを終了する。
3. n が m を割り切るなら、 n を出力してアルゴリズムを終了する。
4. m を n で割った余りを新たに m とし、更に m と n を取り替えて 3. に戻る。
(define (euclid m n)
(if (zero? n) m (euclid n (modulo m n)))

最大公約数とフィボナッチ数って一見何の関わりも無いように見えますよね

fib(0)  = 0　　 　　　　　
fib(1)  = 1
fib(2)  = 0+1                 
fib(3)  = 1+1       2÷1=1余り1        1×1+1=2
fib(4)  = 2+1　　　 3÷2=1余り1        1×2+1=3
fib(5)  = 3+2       5÷3=1余り2        1×3+2=5
fib(6)  = 5+3       8÷5=1余り3        1×3+3=8
fib(7)  = 8+5       13÷8=1余り5       1×8+5=13
fib(8)  = 13+8      21÷13=1余り8      1×13+8=21
fib(9)  = 21+13     34÷21=1余り13     1×21+13=34
fib(10) = 34+21     55÷34=1余り21     1×34+21=55

復習がてらSICPメモを見た時に思い出しました
美しい数字ですね

長くなりましたが

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  (n≧2)

この式をSchemeで書き換えます

(define ( fib n)
  ( cond (( = n 0 )  0)
         (( = n 1 )  1)
         ( else  ( + ( fib ( - n 1))
                     ( fib ( - n 2))))))

この書き方気持ち悪いですね。。。。
id:nishiohirokazuさん とりあえずフィボナッチまで書けました☆