0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....
我們也能將利用遞迴的計算方式寫進程式中，例如，計算以上的費伯納西數列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #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); }}/* 《程式語言教學誌》的範例程式 檔名：recursive2.c 功能：計算費伯納西數列 作者：張凱慶 時間：西元2010年7月 */ |
編譯後執行，如下
計算費伯納西數是利用函數 fabonacii() ，函數內容分成初始條件跟遞迴條件，其中，初始條件在第 19 行
19 20 21 | if (n == 0 || n == 1) { return 1;} |
遞迴條件則在第 23 行
19 20 21 | 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 ，才會陸續得到各個函數值，最後相加得到結果。我們在此不深究遞迴函數是如何運作的，只要知道當遞迴次數越多，所需的記憶體空間也越多，因此會需要更多的計算時間。
另一個常見的遞迴函數例子，就是利用遞迴的方式計算階層數
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #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); }}/* 《程式語言教學誌》的範例程式 檔名：recursive1.c 功能：計算階層 作者：張凱慶 時間：西元2010年7月 */ |
編譯後執行，如下
計算階層數的初始條件為 n 等於 0 或 1 的時候，計算結果為 1 ，反之，遞迴條件回傳 n * factorial(n - 1) ，也就是 n 乘上前一個階乘數。
問題與討論
- 遞迴有什麼優點跟缺點？
- 為什麼遞迴次數越多，所需的記憶體空間也越多？
沒有留言:
張貼留言