■

５つの事なる方法で実装してみる。

 /* 手続き型。通常のループで */
 int fib1(int num){
   int a = 1, b = 0;
   while( num-- > 1 ){
     a += b;
     b = a - b;
   }
   return b;
 }

 /* ２重再帰。一番遅い。 */
 int fib2(int num){
   if (num <= 2)
     return 1;
   else
     return fib2(num-1) + fib2(num-2);
 }

 /* 末尾再帰 */
 int fib3_iter(int num, int a, int b){
   if (num == 1)
     return b;
   else
     return fib3_iter(num-1, a+b, a);
 }
 int fib3(int num){
   return fib3_iter(num, 1, 0);
 }

 /* リンク -lm を忘れないように */
 #include 
 int fib4(int num){
   return (int)(pow*1/2,num))/sqrt(5) + 0.5;
 }

 /* キャッシュを使う */
 #define MAX_CACHE (100)
 int fib5(int num){
   static cache[MAX_CACHE] = {0};

   if (num >= MAX_CACHE) return 0; /* should be error */

   if (cache[num] > 0) return cache[num];

   if (num <= 2)
     cache[num] = 1;
   else
     cache[num] = fib5(num-1) + fib5(num-2):

   return cache[num];
 }

fib(40)として時間を測ってみた、結果は・・・
fib2 だけが極端に遅くて、残りは殆ど同じ。でした。

fib1 が基本。手続き型での記述。
a += b; b = a - b; は　a,b = a+b, a の様な事を、
作業用変数を遣わすに記述。

fib2 は２重再帰。高級言語でこの方法で fib(40) 位試すと、
Pythonでは５分くらい経ってもループが返ってこなかった（汗
C でも少し時間がかかる。同じ計算を何度も繰り返すので効率悪い。

fib3 は末尾再帰。よく見ると fib1 の方法に似ているのが解る。
関数呼び出しの所で、

末尾再帰にすると、ループに置き換えが可能なので
処理系によっては最適化される場合もある。Cではどうだか知らないが、
Schemeや OCaml 等が末尾再帰の最適化をサポートしてる。
JAVA も VM に依っては最適化される場合がある・・・らしい。
と、ibm dWの記事で読んだ。環境に依存するバグ・パターンって記事で。

最適化されなくても、２重再帰に較べると関数の呼び出し回数が減るので、
アルゴリズムの最適化になる。

fib4 の方法は、アルゴリズム辞典に載っていた方法。
精度が気になって、試してみた所 fib(70)位から誤差が出てきた。

意外と早かったのは、２重再帰でキャッシュを使う方法。fib5。
キャッシュが枝刈りに当たるのかな。アルゴリズムはそのままで、
高速化を測る場合に有効。

他の言語でも書いてみたのだけど、大体似たような結果だったけど。
気になったのが Python での最適化方法。

 import psyco
 
 def fib(n):
  if n <= 2:
   return 1
  else:
   return fib(n-1) + fib(n-2)

 psyco.bind(fib)

最適化前は、時間のかかっていた処理でも。
psyco.bin(fib) とすることで、Cと同じ・・・とまではいかなくても、
Cの数倍程度速度が得られた。

*1:1+sqrt(5