我的算法书 - 递归的前进与回溯

一句话算法

递归先一层一层向下调用，遇到边界后再一层一层返回。

问题模型

输入一个正整数 n，先输出 1 2 ... n，换行后再输出 n ... 2 1。

这道题的价值不在输出本身，而在观察递归的两个阶段：

前进阶段：调用下一层递归之前。
回溯阶段：下一层递归返回之后。

核心直觉

把每一次函数调用看成一个小任务。

print_num(dep) 的任务是：

先输出自己 dep。
让 print_num(dep + 1) 完成后面的任务。
等后面的任务结束后，再输出自己 dep。

这就是递归的基本结构：当前层做一点事，把更小的问题交给下一层，下一层回来后，当前层继续完成剩余部分。

算法步骤

定义 print_num(dep)。
如果 dep > n，说明已经越过最后一个数字，输出换行并返回。
输出 dep，这是前进阶段。
调用 print_num(dep + 1)。
再输出 dep，这是回溯阶段。

算法证明

前进阶段： 从 dep = 1 开始，每层递归都会在调用下一层之前输出当前 dep，所以依次输出 1, 2, ..., n。

边界： 当 dep = n + 1 时，递归不再继续，输出换行。

回溯阶段： 返回时，最深层 n 最先继续执行，然后是 n-1，一直回到 1，所以依次输出 n, n-1, ..., 1。

因此输出顺序正确。

复杂度分析

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ ，递归调用栈最多有 n + 1 层。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

        #include <bits/stdc++.h>
using namespace std;

int n;

// dep 表示当前递归深度，也就是正在处理的数字。
void print_num(int dep) {
    if (dep > n) {
        cout << '\n';
        return;
    }

    cout << dep << ' ';   // 递归前进阶段
    print_num(dep + 1);
    cout << dep << ' ';   // 递归回溯阶段
}

int main() {
    cin >> n;
    print_num(1);
    return 0;
}

测试用例

输入：

输出：

1 2 3 4 5
5 4 3 2 1

应用分类详解

这个例子用于理解所有递归算法的运行过程。

一、前进阶段做事

典型模式： 先处理当前节点，再处理子问题。

识别信号： 先序遍历、生成前缀、进入状态时记录。

核心建模： 代码写在递归调用之前。

二、回溯阶段做事

典型模式： 子问题完成后，当前层再汇总或撤销。

识别信号： 后序遍历、撤销选择、统计子树信息。

核心建模： 代码写在递归调用之后。

三、前进和回溯都做事

典型模式： 需要同时记录进入和离开一个状态。

识别信号： 括号序列、DFS 时间戳、递归过程模拟。

核心建模： 递归调用前后各写一段逻辑。

经典例题

树的先序遍历：前进阶段访问节点。
树的后序遍历：回溯阶段访问节点。
DFS 序：进入和离开节点时分别记录时间。

参考

本书相关章节：递归实现多重循环