企业官网建设流程全解析

最近重新整理手头的基础题单，把“我素故我在（深度优先搜索）”“汉诺塔问题的第m步（递归）”“数字游戏（递归）”这三道题连在一起刷了一遍，感触挺深的。127th、128th、129th虽然是三张不同的题面，但内核都在考同一个东西：递归。一个是递归枚举，一个是递归分治，一个是递归跟踪过程。如果你正在准备机试、蓝桥杯或者刚接触算法竞赛，这三道题是非常好的递归入门组合，我今天就把每道题的拆解思路、完整代码和踩过的坑都写出来。

1. 三道题放在一起，其实是在考同一件事

1.1 从“递归三问”说起

很多人一听到递归就头疼，其实递归没有玄学，就三件事：第一，这个函数处理什么问题；第二，问题怎么拆成更小的同类问题；第三，小到什么时候可以直接给答案，也就是出口。只要把这三件事想清楚，代码基本就写出来了。

这三道题恰好对应递归的三种典型用法。“我素故我在”是用递归来遍历一棵搜索树，本质上和深度优先搜索是一回事；“汉诺塔问题的第m步”是利用递归天然的顺序关系，把整个移动过程当作一棵分治树，然后直接定位到某个节点；“数字游戏”则是用递归一步一步跟踪一个数字的变化过程，让你亲眼看见栈是怎么一层层搭起来又一层层弹出去的。

所以别把它当成三道孤立的题，它其实是一整套递归训练。我上课的时候经常跟学生说，把这三题吃透，后面再遇到排列、组合、子集、连通块、二叉树遍历，思路都会顺很多。

1.2 “我素故我在”：DFS 是拿递归做枚举

“我素故我在”这个名字起得有梗，我第一眼还以为是哲学题，后来发现是“素数”的“素”。这类题常见的考法是：给你一个位数 n，让你构造出所有满足条件的数字，条件通常和素数有关。

比如经典到不能再经典的“超级质数”问题：一个 n 位数是超级质数，要求它本身是质数，同时它逐位去掉最后一位之后依然是质数，一直去掉到只剩一位时也必须是质数。这时候你不能直接枚举所有 n 位数再逐个判断，因为 n 一大，数字量是 10 的 n 次方级别，根本跑不完。正确姿势是从最高位开始，每次只追加一位合法的数字，边走边判断素数，这就是典型的深度优先搜索。

它的搜索树长这样：最高位可以是 2、3、5、7（只有这四类一位数质数可以作为根）；第二位的选择就得从 1、3、7、9 里挑，因为如果追加一位后末尾出现了偶数或者 5，这个数必然不是质数，直接剪掉；后面的每一位都类似。每一步都只保留“当前前缀还是质数”的节点，搜索深度到 n 时输出。

DFS 在这种题里的好处就是：它不是盲目枚举十万百万个完整数字，而是每走一步都校验一次，不合格的树枝直接砍掉。搜索树的规模被压得很小，n 在 8 左右时，候选数量都是个位数级别的增长，性能非常稳。

1.3 汉诺塔第m步：递归里藏着顺序

汉诺塔的经典递归大家都会写：要把 n 个盘子从 A 移到 C，先移走上面的 n-1 个盘子到 B，再把最大的盘子挪到 C，最后把 B 上的 n-1 个盘子搬到 C。代码十行以内就能写完。

但“汉诺塔问题的第 m 步”这道题问的不是“打印所有步骤”，而是“只输出第 m 步是哪根柱子移到哪根柱子”。如果你老老实实先跑一遍递归把所有步骤存下来，再取第 m 条，小数据没问题，可 n 稍微一大，2 的 n 次方个步骤根本存不下。这时候必须利用递归的结构，直接判断第 m 步落在递归过程的哪一段。

这个过程可以类比成一棵二叉树的中序遍历：根节点是“移动最大盘子”的那一步，左子树是前 2^(n-1)-1 步，右子树是后 2^(n-1)-1 步。你要找第 m 步，只需要不断判断它落在左子树、根节点还是右子树。落左子树就往左走，落右子树就先把 m 减去左子树和根节点占用的步数，再往右走。这样每一层只走一个方向，时间复杂度只有 O(n)。

这道题的精髓就在于：递归不仅能用来“生成全部答案”，还能用来“定向查找答案”。有时候你想在递归里剪掉一整块完全不需要的子问题，这个思想是通用的。

1.4 数字游戏：递归是过程追踪

第三题的“数字游戏”其实很适合做递归入门，因为它题面直白，过程好玩。常见的版本是给出一个正整数 n，按照规则反复变换直到变成 1：如果是偶数就除以 2，如果是奇数就乘 3 再加 1，要求输出整个变化过程中的数字，或者统计一共经过多少步。

这个规则听起来像游戏，实际上就是角谷猜想，也叫冰雹猜想。虽然还没有人能证明它对所有正整数都一定收敛到 1，但编程实现完全没问题，递归的自然写法就是“如果 n 是 1 就结束，否则根据奇偶性调用 f(n/2) 或 f(3n+1)，并把 n 记下来”。

很多初学者会把这种题写成 while 循环，当然可以，但我更推荐在学生练递归的阶段用递归写一遍。因为递归能让调用顺序变得可见：你每进入一层递归，就相当于把当前数字压进栈里；等递归返回时，还能在“回溯”阶段再做一些输出或者统计。如果只写循环，你体会不到这种先深入再回退的过程。后面学二叉树的先序、中序、后序遍历时，就是这个感觉。

2. “我素故我在”的 DFS 拆解与实现

2.1 典型题面解读

我手头这份题单里的“我素故我在”，题面大意是这样：输入一个正整数 n，输出所有 n 位“超级质数”。超级质数的定义是：该数本身是质数，而且它去掉最后一位得到的数是质数，再去掉一位得到的数还是质数，直到只剩一位时，这一位也必须是质数。

举个例子，n=3 时，233 是超级质数：2 是质数，23 是质数，233 也是质数。而 237 就不行，237 能被 3 整除，不是质数。n 的范围一般不大，常见约束是 1≤n≤8。

输入输出约定一般是：每个符合条件的数字占一行，按字典序从小到大输出。如果没有符合条件的数字，可能要输出一个特定的提示，具体看 OJ 上的要求。这种题的核心点就是：你不可能从 10^(n-1) 到 10^n-1 全枚举一遍，因为那最多有千万级数字，每个都做素数判定的话会非常慢。

2.2 为什么这题必须用 DFS

我们比较一下两种做法。

第一种，暴力枚举所有 n 位数，然后对每个数做素数判定，判断整数的同时还要反复截断再去判断，一个数最差情况下要做 n 次素数判定。n=8 时，9000 万个候选，每个候选做几轮试除，时间直接爆炸，OJ 上基本是超时。

第二种，用 DFS 从高位开始构造。最高位只可能是 2、3、5、7，因为一位数质数就这四个。接下来每一位只可能是 1、3、7、9，因为如果某位让当前数变成以 2、4、6、8、0 结尾，那它一定是偶数；以 5 结尾，那它一定是 5 的倍数。这两种情况都不可能是大于 5 的质数。所以搜索树的每个节点往下最多分四支，深度是 n，规模极小。

这就是深度优先搜索最典型的使用场景：候选答案可以看成一个多阶段决策过程，每一步可选的合法选项有限，而且局部不合法的话，后面的子树根本不用走。DFS 不是用来“优化”暴力的，它本身就是一种比枚举高效的搜索框架。

2.3 搜索状态与剪枝设计

定义一个递归函数 dfs(depth, current)，其中 depth 表示当前已经构造了几位数字，current 是已经构造出的那个整数。

递归要做的事很简单：

1. 如果 depth 等于 n，说明整个数字构造完成，把它输出。
2. 否则，枚举下一位候选数字 nxt，计算 newNum = current * 10 + nxt。
3. 判断 newNum 是否为质数，如果是，递归进入 dfs(depth + 1, newNum)。

这里有一个关键：只需要判断 newNum 是不是质数。因为我们在递归过程中已经保证 current 是质数，只要 newNum 也是质数，那么“逐位去掉最后一位后仍然是质数”的性质就能一路保持下去。

剪枝除了位数限制，就是上面说的候选数字过滤：当前 depth 为 1 时，候选是 2、3、5、7；depth 大于 1 时，候选是 1、3、7、9。这个剪枝不是可选的，是必须的，没有这个过滤，搜索树会膨胀好几倍。

还有一个细节：n=1 时，答案就是 2、3、5、7 四个数字，直接输出即可，不需要进入递归循环。这个边界经常有人漏掉，导致 n=1 时输出为空。

2.4 素数判定怎么写得快

对于这种题，不需要什么米勒-拉宾大素数判定，试除法就够。但是试除必须优化：

• 先从 2 开始判断，如果能被 2 整除就直接返回 false。
• 然后从 3 开始，步长取 2，只试奇数因子。
• 循环上界是 sqrt(x)，不用超过它。

如果用一个函数 isPrime(int x) 单独封装，注意 x=1 要返回 false，x=2 要返回 true。这两个小边界是最容易错的。

更进一步的优化是预处理一个小范围素数表，因为 newNum 最大也只是 10^8 级别，sqrt 在 1 万以内。可以先把 1 万以内的质数用筛法打出来，判断时只用这些素数逐个试除。这样每个数的判定时间极短，整体搜索过程肉眼几乎看不出延迟。

2.5 完整代码与运行示例

下面给一份 C++ 版本，思路最直接。

#include <bits/stdc++.h> using namespace std; int n; bool isPrime(int x) { if (x < 2) return false; if (x == 2) return true; if (x % 2 == 0) return false; for (int i = 3; 1LL * i * i <= x; i += 2) { if (x % i == 0) return false; } return true; } void dfs(int depth, int cur) { if (depth == n) { cout << cur << "\n"; return; } int start = (depth == 1) ? 2 : 1; // 这里处理首位候选：2,3,5,7 // 非首位候选：1,3,7,9 int digits[4]; if (depth == 1) { digits[0] = 2; digits[1] = 3; digits[2] = 5; digits[3] = 7; } else { digits[0] = 1; digits[1] = 3; digits[2] = 7; digits[3] = 9; } for (int i = 0; i < 4; i++) { int nxt = cur * 10 + digits[i]; if (isPrime(nxt)) { dfs(depth + 1, nxt); } } } int main() { cin >> n; if (n == 1) { cout << "2\n3\n5\n7\n"; return 0; } dfs(1, 0); return 0; }

这里唯一要注意的是 dfs(1, 0) 里 depth 从 1 开始，因为我们要构造的是一个 n 位数，最高位不能是 0。首位用 cur=0 进入，乘以 10 再加候选数字，得到的正好是两位数 2 开头的情况。

Python 版本也很短，适合快速验证思路：

import sys sys.setrecursionlimit(10000) def is_prime(x): if x < 2: return False if x == 2: return True if x % 2 == 0: return False i = 3 while i * i <= x: if x % i == 0: return False i += 2 return True def dfs(depth, cur): if depth == n: print(cur) return if depth == 1: cand = [2, 3, 5, 7] else: cand = [1, 3, 7, 9] for d in cand: nxt = cur * 10 + d if is_prime(nxt): dfs(depth + 1, nxt) n = int(input()) if n == 1: print("2\n3\n5\n7") else: dfs(1, 0)

跑一下 n=4，输出前几行应该是 2333、2339、2393、2399 这一串。你可以自己验证一下：2333 去掉最后一位是 233，是质数；233 去掉一位是 23，也是质数；23 去掉一位是 2，还是质数。这就是整道题的核心逻辑。

3. 汉诺塔第m步，怎么做到“只挑一步”

3.1 先回顾经典汉诺塔递归

汉诺塔问题的经典递归代码几乎人人会背：

void hanoi(int n, char src, char aux, char dst) { if (n == 1) { printf("move %d from %c to %c\n", 1, src, dst); return; } hanoi(n - 1, src, dst, aux); printf("move %d from %c to %c\n", n, src, dst); hanoi(n - 1, aux, src, dst); }

这个函数做的事情是把 n 个盘子从 src 搬到 dst，aux 是中间柱子。递归顺序是：先把 n-1 个小盘子搬到 aux，然后把第 n 个大盘子搬到 dst，最后把 aux 上的 n-1 个盘子搬到 dst。

这里有个初学者容易忽略的点：三个柱子的角色是动态的。第一次递归调用里，目标柱是 aux，不是 dst；第三次调用里，源柱变成 aux，目标柱是 dst。你要是把参数顺序搞混，程序跑出来的步骤就是错的。

汉诺塔的总步数是 2^n - 1。这个公式从递归里也能推出来：T(n) = 2T(n-1) + 1，T(1) = 1，解出来就是 T(n) = 2^n - 1。

3.2 第m步到底在第几号线

现在题目要求只输出第 m 步。你可能会想，那我把上面的 hanoi 函数改一改，加个计数器，每移动一次计数器加一，计数到 m 的时候打印。这个思路对是对，但当 m 非常大，比如 n=60，总步数是 2^60-1，你傻乎乎跑完整个递归要跑到地老天荒。

关键思路是“跳过不需要的部分”。递归过程可以看成一个树形结构：

• 第 1 到第 2^(n-1)-1 步，都是“把 n-1 个盘子从 src 搬到 aux”的过程。
• 第 2^(n-1) 步，就是“把第 n 个盘子从 src 搬到 dst”。
• 第 2^(n-1)+1 到第 2^n-1 步，都是“把 n-1 个盘子从 aux 搬到 dst”的过程。

所以给定 m，你可以先判断：

1. 如果 m 小于 2^(n-1)，说明它在左半段，此时要把问题缩小为“n-1 个盘子从 src 搬到 aux 的第 m 步”，目标柱变成了原来的 aux。
2. 如果 m 正好等于 2^(n-1)，那这一步就是移动最大盘的第 n 号盘子，直接输出。
3. 如果 m 大于 2^(n-1)，说明它在右半段，先把 m 减去 2^(n-1)，然后问题变成“n-1 个盘子从 aux 搬到 dst 的第 m' 步”，源柱变成了原来的 aux。

这个过程不断递归下去，每一层只走一个分支，完全不需要进入另一棵子树。所以复杂度从 O(2^n) 降到了 O(n)，这是非常漂亮的优化。

3.3 递归实现与边界处理

实现的时候，递归函数需要四个参数：当前盘子数 n，要找的步数 m，源柱 src，辅助柱 aux，目标柱 dst。

#include <bits/stdc++.h> using namespace std; using ll = long long; void findStep(int n, ll m, char src, char aux, char dst) { if (n == 1) { printf("move %d from %c to %c\n", 1, src, dst); return; } ll half = (1LL << (n - 1)); // 这里相当于 2^(n-1) if (m < half) { findStep(n - 1, m, src, dst, aux); } else if (m == half) { printf("move %d from %c to %c\n", n, src, dst); } else { findStep(n - 1, m - half, aux, src, dst); } } int main() { int n; ll m; cin >> n >> m; findStep(n, m, 'A', 'B', 'C'); return 0; }

代码看着很短，但里面每个参数都很有讲究。

在m < half分支里，调用是findStep(n - 1, m, src, dst, aux)。为什么中间参数是 dst 而不是 aux？因为我们要找的那一步在“把 n-1 个盘子从 src 搬到 aux”的过程里，在这个子问题中，辅助柱变成了 dst，目标柱是 aux。如果你把参数写反了，输出的柱子就不对。

在m > half分支里，调用是findStep(n - 1, m - half, aux, src, dst)，子问题的源柱变成了 aux，辅助柱变成了 src。这两个参数位置是最容易写错的地方，建议自己拿 n=3 的样例手推一遍，理解每个柱子角色为什么互换。

3.4 测试样例与溢出提醒

拿 n=3 来验证。三盘汉诺塔一共 7 步：

1. move 1 from A to C
2. move 2 from A to B
3. move 1 from C to B
4. move 3 from A to C
5. move 1 from B to A
6. move 2 from B to C
7. move 1 from A to C

如果我们调用 findStep(3, 4, 'A', 'B', 'C')，half = 4，m == half，直接输出第 4 步：move 3 from A to C。和手推结果一致。如果 m=2，half=4，m<half，进入 findStep(2, 2, 'A', 'C', 'B')，在这个子问题里 half=2，m==half，输出 move 2 from A to B。这也和完整序列的第 2 步一致。

这里有个非常容易踩的坑：1LL << (n - 1)当 n=64 时会溢出 long long。如果 OJ 数据给了很大的 n 和 m，你需要用 unsigned long long 甚至更严谨的判断方式。比如先判断n > 62时就直接用“第 m 步一定在前半段还是后半段”这种比较大小的方法，而不是先算 2 的幂。一般基础题不会给那么变态，但你要有这个意识。

另外，m 的输入范围要按题目说明来，通常保证 1 ≤ m ≤ 2^n - 1，所以你不必处理 m 越界的情况。如果题目没有保证，你需要在函数开头加一层判断，防止递归到错误的地方。

4. “数字游戏”：让递归自己跑给你看

4.1 题面理解与递归出口

第三题“数字游戏”的题面我见到的常见版本是：输入一个正整数 n，如果 n 是偶数，下一步变成 n/2；如果 n 是奇数，下一步变成 3n+1；一直重复，直到 n 变成 1。要求输出整个变化过程中的数字，从输入的 n 开始，到 1 结束。

举个直观的例子，输入 6，过程是：6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1。输入 3，过程是：3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1。

这道题用递归写特别自然。你先把当前数字输出，然后根据奇偶性调用下一次变换。递归出口是 n 等于 1，因为 1 不能再变，直接结束。

4.2 递归代码实现

#include <bits/stdc++.h> using namespace std; void play(int n) { cout << n; if (n == 1) { cout << "\n"; return; } cout << " -> "; if (n % 2 == 0) { play(n / 2); } else { play(3 * n + 1); } } int main() { int n; cin >> n; play(n); return 0; }

Python 版同理：

def play(n): if n == 1: print(1) return print(n, end=" -> ") if n % 2 == 0: play(n // 2) else: play(3 * n + 1) play(int(input()))

这里有一个输出顺序的细节。如果你把输出放在递归调用后面，输出的顺序就会反过来：变成先输出 1，再输出 2，再输出 4……也就是逆序输出整个序列。我在课上经常拿这个例子考学生，让大家明白“进入递归前输出”和“回溯时输出”是完全不同的效果。前者相当于先序遍历，后者相当于后序遍历。这个感觉在后面的二叉树题目里会反复出现。

4.3 递归调用过程拆解

以 n=3 为例，我们跟一下程序执行顺序：

1. play(3)：输出 3，3 是奇数，调用 play(10)。
2. play(10)：输出 10，10 是偶数，调用 play(5)。
3. play(5)：输出 5，5 是奇数，调用 play(16)。
4. play(16)：输出 16，16 是偶数，调用 play(8)。
5. play(8)：输出 8，8 是偶数，调用 play(4)。
6. play(4)：输出 4，4 是偶数，调用 play(2)。
7. play(2)：输出 2，2 是偶数，调用 play(1)。
8. play(1)：输出 1，返回。

返回的时候，一个函数接一个函数弹出栈。这个“栈”是系统帮你维护的，不需要你自己写任何数据结构。每层调用都保存了自己的局部变量 n，所以当 play(16) 返回后，play(5) 还能继续执行后面的代码。如果后面没有代码了，就直接结束。

我经常让学生手动画出这个调用树，用缩进表示层级。画过三五遍之后，递归基本就开窍了。老话说“递归不画图，等于没学”，有点夸张，但用在入门阶段很有道理。

4.4 变体：如果题目要求“走到第k步的数字”

有时候题面会改成：输入 n 和 k，输出该数字游戏经过 k 步之后的值。这个变体依然可以用递归做，只是多一个参数 step。

int playAt(int n, int k) { if (k == 0) return n; if (n == 1) return 1; if (n % 2 == 0) return playAt(n / 2, k - 1); else return playAt(3 * n + 1, k - 1); }

也有很多同学会想到“统计到 1 一共需要多少步”，那就把递归函数改成返回值累加：

int countSteps(int n) { if (n == 1) return 0; if (n % 2 == 0) return 1 + countSteps(n / 2); return 1 + countSteps(3 * n + 1); }

这个写法非常经典：当前这一步算 1，加上子问题需要的步数。很多递归题的本质都是这样，把“当前一步”加上“剩下的部分”。

如果题目进一步要求“记录这中间出现的最大值”，你可以额外维护一个全局变量或者引用参数。这就是递归题里很常见的设计套路：要么向上层返回一个值，要么通过递归参数把信息传到下层，要么用全局变量在回溯时更新状态。三种方式各有适用场景，练这道题的时候都可以试试。

5. 实战中容易踩的坑与排查技巧

5.1 常见问题速查表

我把最近实际批改作业时遇到的问题整理成了一张表，几乎每个新手都会中招一两项。

5.2 怎么排查“递归永远不结束”

这是最让人崩溃的问题。我的排查方法很简单：先在小输入上手动跟两三步，看看每次递归参数是不是在朝出口方向变化。比如数字游戏里，n 如果是奇数，变到 3n+1 后会变大，再经过偶数的除以 2 又会变小。对于角谷猜想这个具体问题，实测小数据没问题，但如果你的递归参数没有变小，就会无限递归。

还有一个常见原因是出口条件写反了。比如汉诺塔递归里，如果n == 1的出口被漏掉或写成了n == 0，函数会一直调用到负数。写递归时务必把“最小子问题”写清楚，n=0 和 n=1 是完全不同的概念。

如果递归确实很深，超过系统栈上限，进程可能直接崩溃。很多 OJ 上对递归深度没有特殊调整，Python 默认递归限制是 1000，你可以在开头加一行sys.setrecursionlimit(1000000)。C++ 一般不用管，但竞赛里如果递归层数有几万层，建议改成显式栈或循环。

5.3 对拍与测试方法

我强烈推荐一个小技巧：写完汉诺塔第 m 步之后，先写一个打印完整步骤的暴力版本，然后用 n=3、n=4、n=5 把所有 m 都测一遍，对比暴力版本和优化版本的输出。这叫对拍，别看方法土，真的能抓到一大堆参数传错的隐性 bug。

你可以直接写一个脚本，枚举所有 n 和 m，调用两个函数，比对输出。如果有一行不一样，就把这个 m 单独打印出来，基本定位非常快。

对于“我素故我在”，也可以用笨办法验证：暴力枚举 n 位以内所有质数，检查逐位截断性质，再和 DFS 输出对比。DFS 结果对了之后，你会发现它输出的数字一定满足字典序递增，这也是一种自检方式。

5.4 几个延伸话题

这三题练完后，你可以顺势往下玩一些变体。

第一，无向图深度优先搜索。DFS 的应用远不止构造超级质数，图论里的连通块计数、拓扑排序、找环，全都是 DFS 的变形。区别只是搜索节点从“数字前缀”变成了“图中的顶点”，核心框架不变：标记访问、递归邻居、回溯。

第二，快速排序非递归。快速排序本身是递归分治的典型，但有些人为了压栈会改成显式栈模拟。思路就是把“递归函数调用”换成“手动维护一个待处理区间栈”，本质上还是深度优先搜索。理解和写出非递归版，对递归和栈的关系会有更深的体会。

第三，汉诺塔四柱问题。标准汉诺塔是三根柱子，如果变成四根柱子，最优解不再是 2^n-1，常见做法是 Frame-Stewart 算法，里面依然分治递归，但要把“移动 k 个盘子”的划分点枚举一遍取最小值。这是非常优秀的进阶题，能让你把递归动态规划融会贯通。

6. 最后分享一点自己的体会

这几道题我在不同阶段刷过好几遍，每次都有新收获。第一次是刚学递归，照着模板抄，虽然能过但很多细节说不出为什么。第二次是当助教给新生讲题，才逼着自己把每个参数为什么这样传、每棵搜索树为什么长这样彻底搞明白。第三次是重新整理题单时发现，这三个题刚好串起了递归的三条主线：枚举、分治、追踪。

如果你现在正被递归搞得头痛，我的建议很直接：不要背代码，拿一张纸，把调用过程一步一步画出来，画到第十遍的时候你会发现突然通了。就拿这三题当起点，从“我素故我在”的搜索树，到汉诺塔的分治树，再到数字游戏的调用链，画完这三棵树，递归对你来说就不再是玄学了。