“汉诺塔”和“青蛙跳台阶”这两道题大概是技术面试与笔试里出现频率最高的递归入门题。我当面试官的时候经常在算法面试中用它们做“沟通能力”的试金石会背答案的人很多能讲清楚为什么这样递归、递归调用栈怎么变化、换一个条件能不能继续推导的人却很少。这篇文章想聊的不只是把两道题的代码默写出来而是把背后的解决策略拆开揉碎——为什么汉诺塔要这样拆子问题为什么青蛙跳台阶会撞上斐波那契以及面试笔试中你应该怎样组织自己的回答才能真正拿到那一道题的分数。新手可以从这里学会递归入门的骨架有经验的开发者也可以对照检查自己的表达方式。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(fMove 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(fMove 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。这个参数交换的细节是最容易出错的地方也是面试官最爱问的地方。以 n3 为例这段代码会依次输出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) 1T(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 时有两种跳法11或者直接跳 2 级。于是得到一个递推数列f(1) 1f(2) 2f(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)。这里有个很容易写错的细节n1 和 n2 必须单独处理否则初始化 a1、b2 之后n1 会直接返回 b2 导致答案错误。类似的边界问题我后面还会展开细说。如果题目改成“青蛙一次可以跳任意级”那么 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)1f(2)2。然后决定实现方式可以用递归、记忆化递归、自底向上动态规划或滚动变量优化到 O(1) 空间。最后给出复杂度最优解时间 O(n)空间 O(1)。这种表达方式不仅适用于青蛙跳台阶也适用于一切递推动态规划题。先定义状态、再列转移方程、再处理边界、再选择实现是比上来就写代码高一个层次的答题框架。4.3 先画图再写码面试效率翻倍我见过很多候选人憋着不讲话直接在白板上写函数然后程序写了一半才发现参数顺序错了。这里有个小技巧遇到递归题先花 30 秒画一个小规模示例。汉诺塔就画 n3 的移动过程青蛙跳台阶就画一张表竖着写台阶数 1 到 6横着写 f(n)。画图能帮你理清调用关系也能让面试官看到你的思路过程比沉默效率高得多。比如青蛙跳台阶你画到 f(4)5、f(5)8、f(6)13自然会发现它就是斐波那契偏移一位。有了这个发现边界条件检查起来也更轻松。汉诺塔画完 n3 的移动序列你就知道递归函数的三个调用顺序到底长什么样。面试不是闭卷考试你完全可以先举例再抽象。5. 踩坑回忆这三类问题几乎每个人都遇到过5.1 递归深度n 一大程序直接崩溃很多人在本地测试时都遇到过 RecursionError。Python 默认递归深度一般是一千层左右而汉诺塔只要 n1000递归调用深度就是一千层。青蛙跳台阶如果选手写的是暴力递归n1000 时也一样崩溃。要注意“递归调用总次数”和“递归深度”不是一回事。汉诺塔总调用次数是 2^n-1但同一时刻系统栈里最多只有 n 层递归所以空间复杂度是 O(n)。如果你只是被问“移动次数”完全没必要真的递归到底直接算 2^n-1 就行。如果被要求输出步骤n 稍微大一点就已经不现实了因为输出本身的体积就是指数级的。针对递归深度问题可以想到几种应对方式第一把递归改成迭代青蛙跳台阶用滚动变量即可第二汉诺塔可以用显式栈模拟递归但这不是考试重点第三如果只是求移动次数直接使用指数运算。能主动说出这些应对方案面试印象分会明显不同。5.2 大数溢出和取模习惯青蛙跳台阶的答案增长非常快。f(50) 已经超过 20 万亿f(90) 量级巨大在 C 或 Java 里 int 早就装不下了。哪怕是 Python 这种支持大整数的语言在线评测平台也常常要求答案对一个固定大质数取模比如 10^97。取模不是随便加的它要作用在每一次加法之后才能避免中间结果爆炸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 边界条件n0、n1、n2 是最容易丢分的地方边界条件看似简单实际扣分率极高。我总结了一张自查表场景常见错误推荐处理方式汉诺塔 n0没做空输入判断直接进递归n 0 直接返回不输出汉诺塔 n1基础条件只写了递归调用直接打印从 source 到 target青蛙跳台阶 n1忘记初始化 dp[1]单独返回 1青蛙跳台阶 n2误以为只有 1 种返回 2青蛙跳台阶 n0有的题目定义 0 级有 1 种先与面试官确认约定每次写完递归或 DP 代码第一时间用 n0、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)。没有转移关系递归就没有灵魂。第三步写终止条件。汉诺塔的 n1青蛙跳台阶的 n1、n2。终止条件不是可有可无它是递归不再分裂的出口。第四步用小规模输入验证。汉诺塔验证 n3 输出 7 步青蛙跳台阶验证 f(5)8。验证通过后再交代码是一种职业习惯。6.2 自测用例要有“规模梯度”只测试一个用例就提交很容易翻车。我建议每个递归题至少准备三组测试第一组是最小输入比如汉诺塔 n1青蛙跳台阶 n0 或 n1。第二组是小规模常规输入用来核对逻辑汉诺塔 n3、青蛙跳台阶 n5。第三组是稍大一点的输入用来感受性能比如青蛙跳台阶 n100 是否还能秒出结果。如果题目要求输出所有汉诺塔移动步骤n 超过 20 就别强行跑了测试小规模即可。如果只要求次数那么 n1000 也应该能很快速地算出取模结果。把测试用例规划好你就能快速区分“算法逻辑错误”和“性能瓶颈”。6.3 从“会做题”到“会讲题”的三个动作最后说三个面试中很实用的动作。第一个动作先开口讲思路再动手写代码。很多候选人担心沉默太久其实可以边想边说“我打算先写出递推公式然后再实现。如果 n3我可以先模拟一下……”这个等待过程不会让面试官反感。第二个动作写完代码后自己报复杂度不要等面试官来问。给出“时间 O(n)、空间 O(1)”这类结论时顺便说明为什么递归栈深度影响空间复杂度会更显功力。第三个动作主动给出改进方案。青蛙跳台阶从暴力递归升级到滚动变量汉诺塔如果只求次数可以用公式替代递归。这些主动思考是区分“背题选手”和“理解选手”的关键。说句实在话我这些年观察下来能把汉诺塔和青蛙跳台阶讲得透彻的候选人后续面对树、图、动态规划时普遍也更稳。这两道题不是用来背的而是用来练思维的。如果你正在准备面试不妨放下舒适区不看代码拿一张白纸把 n3 的汉诺塔完整走一遍再把青蛙跳台阶的递推表画到 f(10)。等你能对着白纸把自己说服了这两道题才算真正拿下。