斐波那契數列五種實現方式對比：遞歸、迭代、動態數組、new/malloc優化

定義

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)。序列：0,1,1,2,3,5,8,13,21…

1. 朴素遞歸（教學用，生產禁用）

long long Fib(int n) {
    if (n < 2) return n;
    return Fib(n-1) + Fib(n-2); // 指數級複雜度 O(2^n)
}

大量重複計算，n=40已明顯卡頓。

2. 迭代三變量輪換（O(n)時間，O(1)空間）

long long Fib(int n) {
    long long f[3] = {0, 1, n};
    for (int i = 2; i <= n; i++) {
        f[2] = f[0] + f[1];
        f[0] = f[1];
        f[1] = f[2];
    }
    return f[2];
}

無遞歸開銷，適合大n。

3. 固定大小數組備忘錄（O(n)時間，O(n)空間）

long long Fib(int n) {
    long long fib[1000] = {0, 1};
    for (int i = 2; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];
    return fib[n];
}

缺點：n>999越界，不可移植。

4. new 動態分配（修正版，含邊界檢查）

long long Fib(int n) {
    if (n == 0) return 0;
    long long *fib = new long long[n+1];
    fib[0]=0; fib[1]=1;
    for (int i=2; i<=n; i++) fib[i]=fib[i-1]+fib[i-2];
    long long ret = fib[n];
    delete[] fib;
    return ret;
}

5. malloc 動態分配（C 風格）

long long Fib(int n) {
    if (n == 0) return 0;
    long long *fib = malloc(sizeof(long long)*(n+1));
    fib[0]=0; fib[1]=1;
    for (int i=2; i<=n; i++) fib[i]=fib[i-1]+fib[i-2];
    long long ret = fib[n];
    free(fib);
    return ret;
}

性能與適用場景總結

進階：矩陣快速冪 O(log n)

[ F(n+1) ]   [1 1]^n   [1]
[ F(n)   ] = [1 0]    * [0]

適合極大n（如10^18）取模場景。