C語言遞迴與陣列：生成費波那契數列前 20 項

使用遞迴函式 fib(n) 計算費波那契數，並將前 20 項存入陣列列印。遞迴定義：fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)。注意遞迴效率較低，大 n 建議改用迴圈或動態規劃。

程式碼

#include <stdio.h>

int fib(int n);

int main() {
    int i, num[20];
    for (i = 0; i < 20; i++) num[i] = fib(i);
    for (i = 0; i < 20; i++)
        printf("第%2d個費波那契數為:%d\n", i+1, num[i]);
    return 0;
}

int fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return fib(n-1) + fib(n-2);
}

效能補充

遞迴重複計算導致指數時間複雜度。迴圈版本：

int fib_iter(int n) {
    if (n <= 1) return n;
    int a=0, b=1, c;
    for (int i=2; i<=n; i++) { c=a+b; a=b; b=c; }
    return b;
}