爬樓梯問題：遞歸與回溯列印所有爬法

問題描述

有一樓梯共 n 階，每步可跨 1 階或 2 階。求所有可能的爬法組合（而非僅計算總數）。例如 n=3 時，輸出：1-1-1、1-2、2-1。

核心洞察：遞歸結構

到達第 n 階的最後一步，必定來自第 n-1 階（跨 1 步）或第 n-2 階（跨 2 步）。這正是斐波那契遞歸關係：

f(n) = f(n-1) + f(n-2)
基底情況：f(1)=1, f(2)=2

但本題要求列印所有具體路徑，需引入堆疊記錄當前路徑。

算法設計

1. 參數檢查與基底情況

void jump_ladder(int layer, int* stack, int* top) {
    if (layer <= 0) return;           // 非法輸入

    if (layer == 1) {                 // 剩 1 階：只能跨 1
        print_path(1, stack, top);
        return;
    }
    if (layer == 2) {                 // 剩 2 階：1+1 或 2
        print_path(11, stack, top);   // 1,1
        print_path(2, stack, top);    // 2
        return;
    }

    // 遞歸探索：先嘗試跨 1，再嘗試跨 2
    push_and_recurse(layer - 1, stack, top, 1);
    push_and_recurse(layer - 2, stack, top, 2);
}

2. 輔助函數：壓棧、遞歸、彈棧

void _jump_ladder(int layer, int* stack, int* top, int step) {
    stack[(*top)++] = step;           // 記錄本步跨數
    jump_ladder(layer, stack, top);   // 遞歸處理剩餘樓梯
    stack[--(*top)] = 0;              // 回溯：彈出本步
}

3. 路徑列印（利用巨集簡化）

#define PRINT_PATH(code) \
    do { \
        printf(#code); \
        for (int i = 0; i < *top; ++i) \
            printf("%d", stack[i]); \
        printf("\n"); \
    } while(0)

void print_layer_one(int layer, int* stack, int* top) {
    PRINT_PATH(1);
}

void print_layer_two(int layer, int* stack, int* top) {
    PRINT_PATH(11);  // 1+1
    PRINT_PATH(2);   // 2
}

注意：巨集參數 #code 利用字串化運算子將數字常量轉為字串，配合堆疊中已有的步數，構成完整路徑。

完整代碼整合

#include <stdio.h>
#include <assert.h>

#define MAX_STEPS 100

void _jump_ladder(int layer, int* stack, int* top, int step);
void jump_ladder(int layer, int* stack, int* top);

int main() {
    int n = 4;
    int stack[MAX_STEPS] = {0};
    int top = 0;
    jump_ladder(n, stack, &top);
    return 0;
}

// ... 上述所有函數實現 ...

測試與驗證

建議按 n = 1, 2, 3, 4... 遞增測試，人工核對輸出：

• n=1：1
• n=2：11, 2
• n=3：111, 12, 21
• n=4：1111, 112, 121, 211, 22

若輸出符合預期，說明遞歸與回溯邏輯正確。

關鍵點總結

1. 遞歸基底：層數 1、2 直接列印，避免無限遞歸。
2. 堆疊回溯：遞歸前壓棧、返回後彈棧，保證路徑正確。
3. 巨集技巧：do{}while(0) 確保巨集單語句行為，# 運算子實現數字到字串轉換。
4. 測試策略：從小規模手算驗證，逐步擴大測試範圍，防止堆疊溢出或死循環。

此法不僅解決爬樓梯，更是「組合生成」類問題的通用範式。