0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....
我們也能將利用遞迴的計算方式寫進程式中，例如，計算以上的費伯納西數列
#include <stdio.h>
int fabonacii(int n);
int main(void)
{
int i;
for (i = 0; i < 16; i++) {
printf("%d ", i, fabonacii(i));
}
printf("\n");
return 0;
}
int fabonacii(int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
return fabonacii(n - 1) + fabonacii(n - 2);
}
}
/* 《程式語言教學誌》的範例程式
http://pydoing.blogspot.com/
檔名：recursive2.c
功能：計算費伯納西數列
作者：張凱慶
時間：西元2010年7月 */編譯後執行，如下
計算費伯納西數是利用函數 fabonacii() ，函數內容分成初始條件跟遞迴條件，其中，初始條件在第 19 行
if (n == 0 || n == 1) {
return 1;
}遞迴條件則在第 23 行
else {
return fabonacii(n - 1) + fabonacii(n - 2);
}若是 n 為 0 或 1 ，也就是數列中第二個及第三個數字， fabonacii() 回傳 1 ，而 n 大於 2 的話， fabonacii() 回傳 fabonacii(n - 1) + fabonacii(n - 2) ，咦？ fabonacii() 回傳的是呼叫自己。
是的，遞迴函數就是呼叫自己的函數，因為遞迴方式的求解就是把狀況拆解成更簡單的狀況，以計算費伯納西數來說，由於初始的費伯納西數為 0 跟 1 ，其後每個費伯納西數都是前兩個費伯納西數的合，因此 fabonacii() 需要把情況拆解到最初始的狀況才能實際求解，如下圖
所以 fabonacii() 一直反覆呼叫自己到 n 等於 0 及 1 ，才會陸續得到各個函數值，最後相加得到結果。我們在此不深究遞迴函數是如何運作的，只要知道當遞迴次數越多，所需的記憶體空間也越多，因此會需要更多的計算時間。
另一個常見的遞迴函數例子，就是利用遞迴的方式計算階層數
#include <stdio.h>
int factorial(int n);
int main(void)
{
int i;
for (i = 0; i < 10; i++) {
printf("%d! = %d\n", i, factorial(i));
}
return 0;
}
int factorial(int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
return n * factorial(n - 1);
}
}
/* 《程式語言教學誌》的範例程式
http://pydoing.blogspot.com/
檔名：recursive1.c
功能：計算階層
作者：張凱慶
時間：西元2010年7月 */編譯後執行，如下
計算階層數的初始條件為 n 等於 0 或 1 的時候，計算結果為 1 ，反之，遞迴條件回傳 n * factorial(n - 1) ，也就是 n 乘上前一個階乘數。
問題與討論
- 遞迴有什麼優點跟缺點？
- 為什麼遞迴次數越多，所需的記憶體空間也越多？
沒有留言:
張貼留言