C語言遞迴解決爬樓梯問題 (費波那契數列變體)

樓梯 n 階，每步可跨 1 階或 2 階，求走法總數。這是經典的費波那契遞迴關係：f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)。最後一步若跨 1 階則前面有 f(n-1) 種，跨 2 階則 f(n-2) 種。

遞迴實作

#include <stdio.h>

int f(int n);

int main() {
    int num;
    printf("輸入樓梯階數(大於1):");
    scanf("%d", &num);
    printf("上%d階樓梯有%d種方法.\n", num, f(num));
    return 0;
}

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

迭代優化

遞迴重複計算極慢，迭代 O(n) 解法：

int climb(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;
}