斐波那契數算法優化

      在很多算法都用到了遞歸算法，談到遞歸就難免要提到斐波那契數的算法。      最一般的算法如下(C#語法)：         [csharp]  private long Fibonacci(int n)          {              if (n == 1 || n == 2)                  return 1;              else if (n > 2)                  return Fibonacci(n - 1) + Fibonacci(n - 2);              else                  return 0;          }         運行測試下，發現當參數n=39時運行速度就變的很慢了,我計算了下，大概3－4秒,而當n=42時，已然要10來秒才能完成，當n=45時就沒反應了，一兩分鐘都沒有結果。     其實仔細分析下可以Fibonacci方法在被調用後，向下調用就翻倍地調用了下一級的Fibonacci方法。     計算了一下，假設斐波那契數數列的第N項的值是an(n)的話，那麼調用上面的遞歸算法，Fibonacci方法會被調用 an(n) *2 +1 次，當n=39時an(39)=63245986,Fibonacci方法被調用了126491971次，效率之低可以見一斑。    這裡我做了下優化，算法如下： [csharp]   private long Fibonacci(int n,out long m)           {               long t, r;               if (n == 1)               {                   m=0;                   return 1;               }               else if (n == 2)               {                   m = 1;                   return 1;               }               else if (n > 2)               {                   t = Fibonacci(n - 1, out m);                   r = t + m;                   m = t;                   return r;               }               else               {                   m = 0;                   return 0;               }           }     此處的最大優化在於保存計算項之前的每一項的值，每一項的計算只調用Fibonacci方法一次，實際調用Fibonacci方法的次數只有n-1次，如果n=33，那麼調用Fibonacci方法只有32次。     看看方法的調用次數就可知算法的效率了。