C語言經典遞迴：樓梯走法數（費波那契數列）完整解析與非遞迴優化

題目說明

樓梯有 n 階，每步可跨 1 階或 2 階，求不同走法總數。輸入 n，輸出走法數。

數學模型：費波那契數列

• f(1) = 1（只能跨 1 階）
• f(2) = 2（1+1 或 2）
• f(n) = f(n-1) + f(n-2)（最後一步是 1 階或 2 階）

這正是費波那契數列平移版：f(n) = Fib(n+1)

遞迴版代碼（教學用）

#include <stdio.h>

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
}

int main() {
    int n;
    printf("輸入樓梯階數 (n>0): ");
    scanf("%d", &n);
    printf("上 %d 階樓梯有 %d 種走法。\n", n, climbStairs(n));
    return 0;
}

執行畫面

遞迴缺點與三種優化方案

推薦：O(1) 空間迭代寫法

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

延伸應用

• 爬樓梯變體：可跨 1~m 階 → f(n) = Σ f(n-i)
• 最小花費爬樓梯（LeetCode 746）
• 斐波那契在演算法、金融、生物建模的廣泛應用

理解遞迴到迭代的轉換，是演算法優化的核心功力。