遞迴函數

一、費式(Fibonacci)數列

說明:費式數列的前兩項為 1、1,之後的每一項為前兩項之和,即 Fn=Fn-1+Fn-2,費式數列的前 10 項為:1、1、2、3、5、8、13、21、34、55。由使用者輸入一個正數數 n ( n < 40 ),計算出費式數列的第 n 項之值並輸出之。

這個題目我們一樣先假設系統有個函數 F(n) 可以計算費式數列第 n 項之值,於是我們的程式可以寫成:

#include <stdio.h>

void main()

{

 long n;

 scanf("%ld",&n);

 printf("%ld", F(n));

}

因為 F40=102334155 已經超過 int 的範圍,所以我們改用 long 來寫。接下來我們來寫這個函數 F(n),我們知道當 n=1、2 時,F(n)=1,而當 n>2 時,F(n)=F(n-1)+F(n-2),於是我們寫成:

long F(long n)

{

 long a;

 if(n<=2) return 1;

 a=F(n-1)+F(n-2);

 else return a;

}

上面的程式可以再寫得短一點:

long F(long n)

{

 if(n<=2) return 1;

 return F(n-1)+F(n-2);

}

整個程式合併之後如下:

#include <stdio.h>

long F(long n)

{

 if(n<=2) return 1;

 return F(n-1)+F(n-2);

}

void main()

{

 long n;

 scanf("%ld",&n);

 printf("%ld", F(n));

}

 

二、遞迴函數

剛才我們在函數 F(n) 中又呼叫函數 F(n-1) 及 F(n-2),像這樣在函數中又呼叫自己的寫法,就叫做「遞迴 Recursion」,而這種函數就稱為「遞迴函數 Recursive Function」。遞迴函數一開頭要先設定結束條件,否則會無窮循環下去,而遞迴呼叫自己的時候,必須改變它的參數,例如:

int R(int n)

{

 if(結束條件成立) return 預設值;

 return R( n 的運算式 );

}

 

三、練習

  1. 假設一個數列 K 的前兩項是 0、1,而之後的每一項為 Kn=2*Kn-1+3Kn-2,由使用者輸入一個正整數 N,印出該數列的第 N 項。
  2. 將上面的程式改成輸入一個正整數 N,印出數列 K 的前 N 項。
  3. 回到費式數列,改成連續輸入的寫法,輸入一個正整數 N,輸出時印出正整數 N 及第 N 項的值。

 

四、非遞迴式的費式數列:

雖然遞迴函數可以很快地幫我們解決問題,但是它並不是一個有效率的寫法,因為我們在 F(n) 中呼叫了 F(n-1) 及 F(n-2),而 F(n-1) 又會呼叫 F(n-2) 及 F(n-3),如此一來,F(n-2) 就被重複呼叫了,隨著 n 越來越大,這個重複呼叫的次數會越來越大。其實,大部分的程式,我們都可以直接使用迴圈解決,下面我們就使用迴圈來解決費式數列的問題:

#include <stdio.h>

long F(long n)

{

 long a1=0, a2=1, a3=1, i;

 if(n<=2) return 1;

 for(i=3; i<=n; i++) {

   a1=a2;

   a2=a3;

   a3=a1+a2;

 }

 return a3;

}

void main()

{

 long n;

 scanf("%ld",&n);

 printf("%ld", F(n));

}

我們用三個變數 a1、a2、a3 分別記錄 Fn-2、Fn-1、Fn 的值,每經過一次迴圈,就把這三個的值往左位移一次,再計算 a3 的值。上面的程式可以計算出 F46 的值,而且只要一瞬間就完成,而原先用遞迴的寫法,計算 F42 就要花上十幾秒,即可知道遞迴的效率並不是很好。只不過,寫遞迴是省人腦的時間、花電腦的時間,改用迴圈來寫則是省電腦的時間、花人腦的時間,這中間的取捨,就看各位怎麼拿捏了。

 

上一頁

首頁

下一頁