编程中回溯的工作原理？递归回溯代码末尾4条输出语句解析

一、你的代码执行流程拆解 #

先把代码整理成可阅读格式：

func test(currentIndex: Int, op: inout [Int]) {
    // 递归终止条件：currentIndex超过1就返回
    if currentIndex > 1 {
        print("exit here**********************")
        return
    }
    // 第一次递归前的打印
    print("##before", currentIndex)
    // 第一条递归分支：currentIndex+1
    test(currentIndex: currentIndex+1, op: &op)
    // 第一条分支走完后的打印
    print("after------------------------------------------------------", currentIndex)
    // 第二条递归分支：currentIndex+1
    test(currentIndex: currentIndex+1, op: &op)
    // 两条分支都走完后的收尾打印
    print("^^^Final ================  ", currentIndex)
}

var op1: [Int] = []
test(currentIndex: 0, op: &op1)

我们一步步捋清执行顺序，重点解释你疑惑的最后4条输出：

1. 初始调用test(0)，打印##before 0，接着调用test(1)。
2. 进入test(1)，打印##before 1，调用test(2)——触发终止条件，打印exit here后返回。
3. 回到test(1)，打印after...1，再调用test(2)——再次触发终止条件，打印exit here后返回。
4. 回到test(1)，打印^^^Final...1，返回test(0)。
5. 回到test(0)，打印after...0，再次调用test(1)（这是第二条大分支）。
6. 进入test(1)，打印##before 1，调用test(2)——触发终止条件，打印exit here后返回。
7. 回到test(1)，打印after------------------------------------------------------ 1（最后4条的第一条）。
8. 再调用test(2)——触发终止条件，打印exit here**********************（最后4条的第二条），返回。
9. 回到test(1)，打印^^^Final ================ 1（最后4条的第三条），返回test(0)。
10. 回到test(0)，打印^^^Final ================ 0（最后4条的第四条），整个递归结束。

简单说，最后4条是test(0)的第二条递归分支（第二次调用test(1)）执行完后的收尾步骤，以及最外层test(0)的最终收尾。

二、回溯的工作原理 #

回溯本质是深度优先搜索的一种实现方式，核心逻辑就是“一条路走到黑，走不通就退回来换条路”，具体步骤：

• 先做一个选择，然后递归往下探索这个选择的所有可能结果
• 当探索到尽头（触发终止条件）或当前选择不符合要求时，退回到上一步，撤销之前的选择（恢复状态）
• 再做另一个选择，重复上述过程，直到枚举完所有可能的情况

比如常见的排列问题：选第一个元素，递归生成剩下元素的所有排列；然后回溯——把第一个元素放回原位，再选第二个元素，递归生成剩下的排列，以此类推。

你的代码已经具备回溯的核心结构：

• 第一次递归=探索第一条路径
• 中间的print("after...")环节=回溯的“返回/处理”阶段（如果这里有修改op的操作，比如移除元素，就是标准的状态恢复）
• 第二次递归=探索第二条路径

回溯适合处理需要枚举所有可能解的问题，比如子集、组合、迷宫寻路、数独求解等。

内容的提问来源于stack exchange，提问作者Amit