前进与回溯

本节学会什么

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

为什么需要它

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

最小可运行示例

#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。递归调用前是前进，调用返回后是回溯；后面的语句不是没有执行，而是等更深层完成后再执行。

关键过程与易错点

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

动手检查

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

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

立即练习