前进与回溯

本节学会什么

• 区分递归调用前后的两段代码
• 理解“前进时做选择，返回时撤销选择”
• 用输出顺序观察回溯

为什么需要它

递归不仅能计算一个值，也能按路径探索选择。调用下一层前保存当前选择，下一层返回后恢复现场，这个过程称为回溯，是之后搜索和枚举的核心。

最小可运行示例

#include <iostream>

void walk(int depth, int n) {
    if (depth > n) {
        return;
    }
    std::cout << "enter " << depth << '\n';
    walk(depth + 1, n);
    std::cout << "leave " << depth << '\n';
}

int main() {
    walk(1, 3);
    return 0;
}

输出先是 enter 1、enter 2、enter 3，然后才是 leave 3、leave 2、leave 1。递归调用前是前进，调用返回后是回溯；后面的语句不是没有执行，而是等更深层完成后再执行。

flowchart TD
    d1["walk(1)"] --> d2["walk(2)"]
    d2 --> d3["walk(3)"]
    d3 --> stop["walk(4): 到达边界"]
    stop --> leave3[leave 3]
    leave3 --> leave2[leave 2]
    leave2 --> leave1[leave 1]

    classDef forward fill:#dcefe9,stroke:#087c6c,color:#202827
    classDef boundary fill:#fff4db,stroke:#b76e00,color:#202827
    classDef backtrack fill:#fbe3dd,stroke:#b9472f,color:#202827
    class d1,d2,d3 forward
    class stop boundary
    class leave3,leave2,leave1 backtrack

关键过程与易错点

• 在递归调用前修改状态，必须在调用后恢复状态，否则下一个分支会带着上一个分支的数据。
• 输出或记录答案常在边界条件处完成，因为那时一个完整选择已经形成。
• 不要把“回溯”理解为自动撤销所有变量。只有你明确写出的恢复操作才会发生。
• 调试时给 depth 加缩进输出，比盯着很多次函数调用更直观。

动手检查

将示例改成先输出 depth、递归、再输出 depth，用空格分隔。对 n = 3 写出预期序列后再运行。

定义全局整数 chosen，递归前加一、递归后减一，在每层输出它，确认返回时恢复到了进入该层前的值。

立即练习