kowala's home: Dev C++ 有趣的遞迴函數-費式數列(Fibonacci)

2011-10-25

Dev C++ 有趣的遞迴函數-費式數列(Fibonacci)

C 語言有個好玩的寫法，就是遞迴函數(Recursive call)，遞迴函數有幾項特徵，就是

1.自己呼叫自己
2.必須存在終止條件

來找個例子，一般談到遞迴，總是喜歡拿費式數列(Fibonacci)來說明，這裡也簡單的介紹一下，詳細的資料可以在維基百科[1]找到。

費式數列(Fibonacci)
數列的前兩項為 1、1，之後的每一項為前兩項之和，
即 Fn=Fn-1+Fn-2，數列的前 10 項為：
1、1、2、3、5、8、13、21、34、55、89。

是使用一種線性遞迴關係式來定義：

$F_{0} = 0 \,$

$F_{1} = 1 \,$

$F_{n} = F_{n-1}+F_{n-2} \,$

設若: $F_{n} / F_{n-1}\,$ 當n趨於無限大之極限值存在，則其值為 $1+\sqrt{5} \over 2\,$ = Φ 恰為黃金分割之ㄧ值，1.618....，另一值則為0.618....，兩值互為倒數，也就是說1.618....分之1=0.618....，反之亦然。

我們任意取兩個連續的數來除，很容易可以得到一比值

    89/55=1.618181818181...
    55/34=1.617647058823...
    34/21=1.619047619047...
    21/13=1.615384615384...
    13/8=1.625
    8/5=1.6
    5/3=1.66666666666666...

這就是有名的黃金比例 1.618...

好了，介紹到這裡，讓我們來看看如何在 C++ 中實現...

這是費式數列(Fibonacci)的寫法，C++可以很簡潔的表示出來[2].

double f(double n){
    if(n<=2)return 1;
    return f(n-1)+f(n-2);
}

簡單說明一下遞迴函數的特徵

if(n<=2)return 1;          這是中止條件
return f(n-1)+f(n-2);    這是自己呼叫自己

來實做一下
//-----------------------------------------------------------
#include <cstdlib>
#include <iostream>
#include <iomanip.h>

using namespace std;

//費式數列(Fibonacci)
double f(double n){
   if(n<=2)return 1;
   return f(n-1)+f(n-2);
}
int main(int argc, char *argv[]){
   int i,n;
   system("cls");

   cout << "遞迴測試 - 費式數列(Fibonacci)" << endl;
   cout << "------------------------------" << endl;

   n=30;
   for(int i=1;i<=n;i++){
       cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i
       << setw(10) << setprecision(10) << setfill(' ')<< f(i) << "\n";
   }

   cout << "\n黃金比例 (f(9)/f(8)) = " << f(9)/f(8) << endl << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

//-----------------------------------------------------------

結果如下

這個是為了對齊而對 cout 做了一些指定
cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i

setw(5) 設定5個字組寬
setprecision(5) 設定5個數字
setfill(' ') 空格補 space

為了觀察遞迴函數的運作，我們在裏頭加一行顯示其值，如下

double fi(double n){
    cout << n << " ";
    if(n<=2)return 1;
    return fi(n-1)+fi(n-2);
}

再把 n 改小一點，n=10，再跑看看

   n=10;
   for(int i=1;i<=n;i++){
       cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i
       << setw(10) << setprecision(10) << setfill(' ')<< fi(i) << "\n";
   }