“汉诺塔”和“青蛙跳台阶”这两道题，大概是技术面试与笔试里出现频率最高的递归入门题。我当面试官的时候，经常在算法面试中用它们做“沟通能力”的试金石：会背答案的人很多，能讲清楚为什么这样递归、递归调用栈怎么变化、换一个条件能不能继续推导的人，却很少。这篇文章想聊的不只是把两道题的代码默写出来，而是把背后的解决策略拆开揉碎——为什么汉诺塔要这样拆子问题，为什么青蛙跳台阶会撞上斐波那契，以及面试笔试中你应该怎样组织自己的回答，才能真正拿到那一道题的分数。新手可以从这里学会递归入门的骨架，有经验的开发者也可以对照检查自己的表达方式。
1. 为什么面试官总拿这两道题“试水温”
1.1 它们表面上考递归，实际考的是拆解问题的能力
递归的核心，是“把一个大规模问题，转化成若干个结构相同、规模更小的子问题”。汉诺塔和青蛙跳台阶，恰好是两种最典型的递归形态。
汉诺塔展示的是“分治式递归”：你没法直接移动 n 个盘子，但你可以把问题拆成移动 n-1 个盘子、移动 1 个盘子、再移动 n-1 个盘子。这里最难的是理解子问题是怎样复用的，以及递归参数为什么会来回交换。而青蛙跳台阶展示的是“递推式递归”：当前状态和前面几个状态有确定的数量关系，f(n) 由 f(n-1) 和 f(n-2) 组合得到。这其实就是动态规划的前身。
所以面试官选这两道题，真正想看的是你对“将大问题变小问题”这件事的熟练程度。能把这种拆解讲明白的人，往往在面对树的遍历、图的搜索、归并排序、分治算法时，思路也更容易跟得上。反过来，只会把代码背下来，一旦被追问“为什么要分成这三步”“为什么不能先把最大盘子移开”，马上就露馅了。
1.2 两道题刚好评测两种互补的思维模式
汉诺塔更强调“调用顺序”：递归不是简单的数学公式，而是多个子任务按特定顺序执行。一个函数在还没跑完时，又调用了自己，这对初学者来说是第一道坎。青蛙跳台阶则更强调“状态依赖”：答案不是靠一步步操作生成的，而是靠公式叠加出来的。前者像你在按步骤完成一盘棋，后者像你根据上一层的砖数推算出下一层的砖数。
把这两道题放在一起看，正好覆盖了递归的两大侧面：
| 题目 | 核心考察点 | 代码难度 | 常见扩展方向 |
|---|---|---|---|
| 汉诺塔 | 子问题拆分、参数交换、递归栈顺序 | 低 | 输出步骤、移动次数公式、四柱变体 |
| 青蛙跳台阶 | 递推关系、边界条件、重复计算 | 低 | 一次跳多级、记忆化搜索、动态规划、取模 |
1.3 “背诵党”最怕的追问方向
我经常在候选人写完代码后追加几个问题：
第一个，汉诺塔移动次数是多少？为什么是 2 的 n 次方减 1？第二个，如果青蛙一次能跳 1 级、2 级或 3 级，递推式该怎么改？第三个，如果青蛙一次能跳任意级，答案是多少？第四个，n 很大的时候递归会栈溢出，怎么改成迭代？
这些问题没有一个是超纲的，全部建立在同一个递推思想上。但如果候选人对题目的理解只停留在“抄过一遍代码”，大概率答不上来。所以这两道题不是简单题，而是很好的水平探测器。
2. 汉诺塔的递归骨架：三步拆分与“信任函数”思维
2.1 核心拆分：把最大盘子当成“关键路径”
汉诺塔问题描述很简洁：有三根柱子，初始时所有盘子按从大到小叠在柱子 A 上，要把全部盘子移动到柱子 C，过程中大盘子永远不能压在小盘子上面。很多初学者上来就会去模拟“第一步应该怎么动”，结果发现情况多到不可控。
正确思路是反过来的：不要急着想第一步，先想“最大那个盘子什么时候才能动”。最大的盘子一开始在 A，目标在 C。它一旦离开 A，就再也不能被别的小盘子压住，所以它必须是 A 柱上最后一个被移动的盘子。想要把最大盘子从 A 移到 C，前提条件是：A 柱上除了它以外没有别的盘子，C 柱上也没有任何盘子。也就是说，上面的 n-1 个盘子必须全部被移到 B 柱上，并且按顺序堆好。
于是问题分裂成三个阶段：
- 把 A 上的 n-1 个盘子，借助 C，整体移动到 B。
- 把最底下的第 n 个盘子，从 A 直接移动到 C。
- 把 B 上的 n-1 个盘子，借助 A，整体移动到 C。
阶段 1 和阶段 3，本质上都是“移动 n-1 个盘子”的汉诺塔问题，只是起始柱、目标柱、辅助柱的角色发生了变化。这就构成了递归。你不用去关心 n-1 个盘子内部每一步怎么走，因为下一次递归调用会替你处理。这种“相信函数能解决子问题”的心态，是所有递归代码的基础。
2.2 代码落地：递归函数的三段式结构
用 Python 实现时，函数参数建议写成 source、target、auxiliary，也就是起始柱、目标柱、辅助柱。我见过很多同学参数顺序写反，代码看起来没大问题，一跑就乱。
def hanoi(n, source, target, auxiliary): if n == 1: print(f"Move disk 1 from {source} to {target}") return # step 1: move n-1 disks from source to auxiliary hanoi(n - 1, source, auxiliary, target) # step 2: move the largest disk from source to target print(f"Move disk {n} from {source} to {target}") # step 3: move n-1 disks from auxiliary to target hanoi(n - 1, auxiliary, target, source)第一次递归调用时，原本的 target 变成了辅助柱，因为你要先把上方的小盘子暂时放到 B 上去；第二次递归调用时，原本的 auxiliary 变成了起始柱，因为小盘子已经堆在 B 上了，现在要把它们搬到 C。这个参数交换的细节，是最容易出错的地方，也是面试官最爱问的地方。
以 n=3 为例，这段代码会依次输出：
Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C总共 7 步。手动走一遍这个输出，你对递归调用顺序的理解就会上一个台阶。
2.3 移动次数为什么是指数爆炸
如果只问最少需要移动多少次，不需要真的列步骤。设移动 n 个盘子需要 T(n) 次，按前面的拆分，先移动 n-1 个盘子到辅助柱，再移动 1 个最大盘，再移动 n-1 个盘子到目标柱。于是：
T(1) = 1
T(n) = 2 * T(n-1) + 1
展开一下：
T(n) = 2 * (2 * T(n-2) + 1) + 1 = 4 * T(n-2) + 2 + 1
继续展开到 T(1)，可得 T(n) = 2^n - 1。这个公式说明移动次数随盘子数量指数增长。有 20 个盘子就要移动 1,048,575 步；有 64 个盘子，数字大得超出直觉。这也是为什么在实际工程中，递归不能盲目用在规模很大的场景里。
在面试中考这个问题，核心不是让你背公式，而是看你能不能通过递推式自己推导出来。先写递推式，再展开求和，是比直接说出结果更有说服力的回答方式。
3. 青蛙跳台阶与斐波那契：从暴力递归到动态规划
3.1 递推公式：从“最后一步”开始归纳
青蛙跳台阶的标准版本是：一只青蛙要跳到第 n 级台阶，每次可以跳 1 级或 2 级，问一共有多少种不同跳法。
不要从第一步开始分类，会越想越乱。正确策略是看“最后一步”。要到达第 n 级台阶，青蛙只可能是从第 n-1 级跳 1 级上来，或者从第 n-2 级跳 2 级上来。这两种情况互斥，又覆盖了所有可能，所以跳法总数 f(n) 等于 f(n-1) 加上 f(n-2)。
边界条件是：
- n = 1 时，只有一种跳法：跳 1 级。
- n = 2 时，有两种跳法：1+1，或者直接跳 2 级。
于是得到一个递推数列：
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)，n > 2
这个数列和斐波那契数列很像，只是初始值从 1、1 变成了 1、2。如果某些解法里把 f(0) 定义为 1，那么 f(2) = f(1) + f(0) = 2 也能对得上。但面试时最好按状态定义来讲，别含糊。
3.2 暴力递归：好写，但会重复计算
最直观的代码是直接按递推式写递归：
def climb_stairs(n): if n == 1: return 1 if n == 2: return 2 return climb_stairs(n - 1) + climb_stairs(n - 2)这段代码非常好理解，但性能很差。画一下递归树就会发现，climb_stairs(3) 会被重复计算很多次。比如想算 climb_stairs(6)，需要分别算 5 和 4；算 5 又需要算 4 和 3；于是 4 被算了两次，3 出现三次以上。整个调用次数近似 2 的指数次。
实际运行的时候，n 到 40 左右就已经明显卡顿，n 到 100 基本算不出来。面试中如果只写出这段，面试官通常会追问“时间复杂度多少？有什么改进办法？”。
改进思路很简单：既然很多结果是重复的，那就把它们存下来。第一次算完 f(5)，下次再需要 f(5) 的时候直接查表返回。
memo = {} def climb_stairs(n): if n == 1: return 1 if n == 2: return 2 if n not in memo: memo[n] = climb_stairs(n - 1) + climb_stairs(n - 2) return memo[n]这种“先递归，边算边存”的方法叫记忆化搜索，是动态规划的近亲。
3.3 自底向上填表：动态规划的第一课
记忆化搜索是自顶向下的思路，从大问题出发，拆到小问题。另一种更工程化的做法是自底向上：先算出 f(1)、f(2)，再用它们算出 f(3)、f(4)，一路填到 f(n)。
def climb_stairs_dp(n): if n == 1: return 1 if n == 2: return 2 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]dp[i] 表示跳到第 i 级台阶的总跳法。for 循环里做的事情，就是执行状态转移方程 dp[i] = dp[i-1] + dp[i-2]。这种写法的时间复杂度是 O(n)，空间复杂度是 O(n)。
动态规划的难点不在写循环，而在两件事：第一，把 dp[i] 的状态定义说出来；第二，把状态转移方程写出来。青蛙跳台阶正是练习这两件事的最小规模题目，所以它是非常经典的动态规划入门题。
3.4 两个滚动变量：把空间压到 O(1)
观察状态转移方程，dp[i] 永远只依赖前两个数。也就是说，我们根本不需要保存整个数组，只需保存“当前前一个”和“当前前两个”的值。
def climb_stairs_inplace(n): if n == 1: return 1 if n == 2: return 2 a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b循环里的 a 相当于 f(i-2)，b 相当于 f(i-1)，赋值之后它们分别推进为 f(i-1) 和 f(i)。最终 b 就是 f(n)。这个写法的时间复杂度依然是 O(n)，但空间复杂度从 O(n) 降到了 O(1)。
这里有个很容易写错的细节：n=1 和 n=2 必须单独处理，否则初始化 a=1、b=2 之后，n=1 会直接返回 b=2 导致答案错误。类似的边界问题，我后面还会展开细说。
如果题目改成“青蛙一次可以跳任意级”，那么 f(n) = f(n-1) + f(n-2) + ... + f(1) + 1，两式相减可得 f(n) = 2 * f(n-1)，所以 f(n) = 2^(n-1)。这种变体同样常见，本质上就是换个递推关系。
4. 比写代码更重要的：面试官想听到的“推导过程”
4.1 汉诺塔的标准口头推导模板
很多候选人一写代码就闷头开干，结果代码写出来了，却解释不清楚。其实面试官最想听的是思路推导，不是代码本身。
我会建议用这个顺序去讲汉诺塔：
第一句话，先定性：“这个问题可以用递归解决，因为移动 n 个盘子可以拆成两个规模为 n-1 的同类问题。”
第二句话，讲拆分：“先把上面 n-1 个盘子从起始柱移到辅助柱；再把第 n 个盘子从起始柱移到目标柱；最后把 n-1 个盘子从辅助柱移到目标柱。”
第三句话，讲递归参数：“后两个操作中，起始柱和目标柱发生了变化，所以递归函数里的 source、target、auxiliary 要交换。”
第四句话，讲终止条件：“当 n 等于 1 时，直接移动一次即可。”
最后补充复杂度：“每层递归会把问题拆成两个子问题，所以总次数是 2^n-1，空间复杂度是递归深度 O(n)。”
这套话术能把你从“我会写”变成“我讲得清”。面试官听到这种答案，就已经不需要再追问你为什么了。
4.2 青蛙跳台阶的标准口头推导模板
青蛙跳台阶也一样，线性的表达顺序会让思路显得特别干净：
- 先定义状态：f(n) 表示跳到第 n 级台阶的总跳法。
- 再分情形：最后一步只能有两种可能，从第 n-1 级跳 1 级，或从第 n-2 级跳 2 级。
- 因此写出递推：f(n) = f(n-1) + f(n-2)。
- 再写边界：f(1)=1，f(2)=2。
- 然后决定实现方式：可以用递归、记忆化递归、自底向上动态规划，或滚动变量优化到 O(1) 空间。
- 最后给出复杂度：最优解时间 O(n)，空间 O(1)。
这种表达方式不仅适用于青蛙跳台阶，也适用于一切递推动态规划题。先定义状态、再列转移方程、再处理边界、再选择实现，是比上来就写代码高一个层次的答题框架。
4.3 先画图再写码，面试效率翻倍
我见过很多候选人憋着不讲话，直接在白板上写函数，然后程序写了一半才发现参数顺序错了。这里有个小技巧：遇到递归题，先花 30 秒画一个小规模示例。
汉诺塔就画 n=3 的移动过程；青蛙跳台阶就画一张表，竖着写台阶数 1 到 6，横着写 f(n)。画图能帮你理清调用关系，也能让面试官看到你的思路过程，比沉默效率高得多。
比如青蛙跳台阶，你画到 f(4)=5、f(5)=8、f(6)=13，自然会发现它就是斐波那契偏移一位。有了这个发现，边界条件检查起来也更轻松。汉诺塔画完 n=3 的移动序列，你就知道递归函数的三个调用顺序到底长什么样。面试不是闭卷考试，你完全可以先举例再抽象。
5. 踩坑回忆：这三类问题几乎每个人都遇到过
5.1 递归深度：n 一大，程序直接崩溃
很多人在本地测试时都遇到过 RecursionError。Python 默认递归深度一般是一千层左右，而汉诺塔只要 n=1000，递归调用深度就是一千层。青蛙跳台阶如果选手写的是暴力递归，n=1000 时也一样崩溃。
要注意“递归调用总次数”和“递归深度”不是一回事。汉诺塔总调用次数是 2^n-1，但同一时刻系统栈里最多只有 n 层递归，所以空间复杂度是 O(n)。如果你只是被问“移动次数”，完全没必要真的递归到底，直接算 2^n-1 就行。如果被要求输出步骤，n 稍微大一点就已经不现实了，因为输出本身的体积就是指数级的。
针对递归深度问题，可以想到几种应对方式：第一，把递归改成迭代，青蛙跳台阶用滚动变量即可；第二，汉诺塔可以用显式栈模拟递归，但这不是考试重点；第三，如果只是求移动次数，直接使用指数运算。能主动说出这些应对方案，面试印象分会明显不同。
5.2 大数溢出和取模习惯
青蛙跳台阶的答案增长非常快。f(50) 已经超过 20 万亿，f(90) 量级巨大，在 C++ 或 Java 里 int 早就装不下了。哪怕是 Python 这种支持大整数的语言，在线评测平台也常常要求答案对一个固定大质数取模，比如 10^9+7。
取模不是随便加的，它要作用在每一次加法之后，才能避免中间结果爆炸：
MOD = 10**9 + 7 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) % MOD汉诺塔的移动次数 2^n - 1 同样可能非常大。如果要求输出结果，常规的做法是用快速幂取模。这里核心教训是：看到“递推增长很快”的字眼，你就应该条件反射地思考溢出和取模。这是从算法题通往工程习惯的一步。
5.3 边界条件：n=0、n=1、n=2 是最容易丢分的地方
边界条件看似简单，实际扣分率极高。我总结了一张自查表：
| 场景 | 常见错误 | 推荐处理方式 |
|---|---|---|
| 汉诺塔 n=0 | 没做空输入判断，直接进递归 | n <= 0 直接返回，不输出 |
| 汉诺塔 n=1 | 基础条件只写了递归调用 | 直接打印从 source 到 target |
| 青蛙跳台阶 n=1 | 忘记初始化 dp[1] | 单独返回 1 |
| 青蛙跳台阶 n=2 | 误以为只有 1 种 | 返回 2 |
| 青蛙跳台阶 n=0 | 有的题目定义 0 级有 1 种 | 先与面试官确认约定 |
每次写完递归或 DP 代码，第一时间用 n=0、1、2、3 跑一遍，就能发现绝大多数问题。这一步比反复检查代码逻辑更便宜。
6. 从两道题抽象一套“递归类问题”通用解题套路
6.1 四步走：状态、转移、边界、验证
汉诺塔和青蛙跳台阶虽然外表不同，但解题流程完全一致。
第一步，定义函数或状态的含义。汉诺塔里 hanoi(n, source, target, auxiliary) 表示把 n 个盘子从 source 移到 target；青蛙跳台阶里 f(n) 表示跳到第 n 级的跳法总数。状态定义不清楚，后面全乱。
第二步，找状态转移关系。汉诺塔把 n 拆成 n-1；青蛙跳台阶把 f(n) 拆成 f(n-1) 加 f(n-2)。没有转移关系，递归就没有灵魂。
第三步，写终止条件。汉诺塔的 n=1；青蛙跳台阶的 n=1、n=2。终止条件不是可有可无，它是递归不再分裂的出口。
第四步，用小规模输入验证。汉诺塔验证 n=3 输出 7 步；青蛙跳台阶验证 f(5)=8。验证通过后再交代码，是一种职业习惯。
6.2 自测用例要有“规模梯度”
只测试一个用例就提交，很容易翻车。我建议每个递归题至少准备三组测试：
第一组是最小输入，比如汉诺塔 n=1，青蛙跳台阶 n=0 或 n=1。第二组是小规模常规输入，用来核对逻辑，汉诺塔 n=3、青蛙跳台阶 n=5。第三组是稍大一点的输入，用来感受性能，比如青蛙跳台阶 n=100 是否还能秒出结果。
如果题目要求输出所有汉诺塔移动步骤，n 超过 20 就别强行跑了，测试小规模即可。如果只要求次数，那么 n=1000 也应该能很快速地算出取模结果。把测试用例规划好，你就能快速区分“算法逻辑错误”和“性能瓶颈”。
6.3 从“会做题”到“会讲题”的三个动作
最后说三个面试中很实用的动作。
第一个动作，先开口讲思路，再动手写代码。很多候选人担心沉默太久，其实可以边想边说：“我打算先写出递推公式，然后再实现。如果 n=3，我可以先模拟一下……”这个等待过程不会让面试官反感。
第二个动作，写完代码后自己报复杂度，不要等面试官来问。给出“时间 O(n)、空间 O(1)”这类结论时，顺便说明为什么递归栈深度影响空间复杂度，会更显功力。
第三个动作，主动给出改进方案。青蛙跳台阶从暴力递归升级到滚动变量；汉诺塔如果只求次数，可以用公式替代递归。这些主动思考，是区分“背题选手”和“理解选手”的关键。
说句实在话，我这些年观察下来，能把汉诺塔和青蛙跳台阶讲得透彻的候选人，后续面对树、图、动态规划时，普遍也更稳。这两道题不是用来背的，而是用来练思维的。如果你正在准备面试，不妨放下舒适区，不看代码，拿一张白纸，把 n=3 的汉诺塔完整走一遍，再把青蛙跳台阶的递推表画到 f(10)。等你能对着白纸把自己说服了，这两道题才算真正拿下。
