您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

遞歸函數返回值陷阱：李白買酒問題中遞歸回溯缺少返回值導致結果為 0 的根因分析

編輯：程式設計綜合問答

問題代碼


int fun(int store, int flower, int wine, int i) {
    if (store > 5 || flower > 10) return 0;
    else if (store == 5 && flower == 10 && i == 15) {
        if (wine == 0 && a[14] == 'b') count++;
    }
    a[i] = 'a';
    fun(store+1, flower, wine*2, i+1);  // ❌ 忽略返回值
    a[i] = 'b';
    fun(store, flower+1, wine-1, i+1);  // ❌ 忽略返回值
    return count;  // 全局變量 count 干擾遞歸純度
}

核心錯誤：遞歸調用未接收返回值

遞歸函數**必須**將子問題的返回值聚合：


// 錯誤：調用後不接收返回值
fun(...);

// 正確：聚合子問題結果
int left = fun(...);
int right = fun(...);
return left + right;

修正版：純函數式遞歸（無全局變量）


int dfs(int store, int flower, int wine) {
    // 剪枝：超出限制
    if (store > 5 || flower > 10) return 0;
    // 終止條件：最後一次必須是花(flower=10)，酒剛好喝完(wine=1)
    // 注意：題目說「最後一次遇到的是花」，所以遞歸到 flower=10 時 wine 應為 1（喝完變 0）
    if (store == 5 && flower == 9 && wine == 1) return 1;
    
    int total = 0;
    // 遇店：酒翻倍
    total += dfs(store + 1, flower, wine * 2);
    // 遇花：喝一斗(酒-1)
    total += dfs(store, flower + 1, wine - 1);
    return total;
}

int main() {
    printf("總方案數: %d\n", dfs(0, 0, 2));  // 初始酒 2 斗
    return 0;
}

狀態空間分析

總狀態數 ≤ 6 × 11 × 33 = 2178，極小，遞歸無性能問題。

為什麼原代碼輸出 0？

全局 `count` 未初始化（C語言全局自動初始化為 0，這倒不是主因）
**主因**：遞歸調用 `fun(...)` 返回值被丟棄，`count` 只在最深層 `if` 中 `++`，但該層返回值未被上層接收累加
`return count` 返回的是全局變量，但遞歸樹中只有滿足條件的葉子節點會 `count++`，且無返回值傳遞，最終 `main` 打印的是 `fun(0,0,2,0)` 的返回值，即最外層調用的 `return count`，此時 `count` 可能已被修改，但邏輯混亂

帶路徑記錄版本


void dfsPath(int store, int flower, int wine, string path) {
    if (store > 5 || flower > 10) return;
    if (store == 5 && flower == 9 && wine == 1) {
        cout << path + "b" << endl;  // 最後必是花
        return;
    }
    dfsPath(store + 1, flower, wine * 2, path + "a");
    dfsPath(store, flower + 1, wine - 1, path + "b");
}

int main() {
    dfsPath(0, 0, 2, "");
    return 0;
}