★ FEATURED ARTICLE 1. 从两个老题看递归的本质汉诺塔和青蛙跳台阶几乎是每一本算法书、每一门编程语言课都会碰到的两个题目。很多人第一次学递归就是从这两道题开始的。但奇怪的是相当一部分人学完之后能背出汉诺塔的代码却说不清楚为什么那样写是对的能算出青蛙跳台阶的答案却不知道递归和迭代到底差在哪里。我自己当年也是这样直到后来在项目里真正用递归去处理树形结构、解析嵌套配置才回过头把这两个题重新啃了一遍。这篇文章不打算写成教科书式的题解。我想做的是把这两个经典问题拆开揉碎讲清楚递归到底是怎么运转的、每一步为什么这么设计、代码写出来之后计算机在背后做了什么。同时也会把实际写代码时容易踩的坑、性能上的取舍、以及从这两个题延伸出去的真实应用场景一并聊透。不管你是刚接触递归的新手还是想重新梳理一遍基础的老手应该都能从里面拿到点东西。核心关键词会贯穿全文递归、汉诺塔、青蛙跳台阶、递归出口、栈帧、记忆化、动态规划。这些词不是摆设每一个我都会结合具体代码和场景讲明白它到底指什么。2. 递归到底是怎么回事2.1 用生活场景理解递归递归这个词听起来玄乎其实核心就一句话一个函数在运行过程中调用了它自己。但光这么说太抽象我用一个生活场景来解释。假设你在一排很长的队伍里想知道自己前面有多少人。你不想一个个数于是问你前面那个人“你前面有多少人”前面那个人也不知道于是他又问他前面的人一直往前传。直到问到队伍最前面的那个人他说“我前面没人是0。”然后这个答案一层层往回传每个人把自己加上去最后传到你这里你就知道了自己的位置。这个过程就是递归的两个关键动作递和归。“递”是不断把问题往前推推到最简单的情况“归”是从最简单的情况开始一层层把结果带回来。汉诺塔和青蛙跳台阶本质上都是这个逻辑。2.2 递归出口为什么是命根子写递归最容易犯的错就是忘记写或者写错递归出口也叫基准情况。递归出口就是那个“队伍最前面的人”它告诉函数什么时候该停下来。没有它函数就会无限调用自己直到把栈空间撑爆程序直接崩溃报出那个经典的StackOverflowError。我见过不少初学者写青蛙跳台阶代码写成这样public int jump(int n) { return jump(n - 1) jump(n - 2); }这段代码逻辑上没错但少了出口。当 n 减到负数时它还在继续调用永远不会停。正确的写法必须先把 n1 和 n2 的情况定死让递归有终点。递归出口的设计有个原则它必须是最小规模、可以直接给出答案的情况。汉诺塔里是“只剩一个盘子”青蛙跳台阶里是“剩一级或两级台阶”。找到这个最小情况递归才有落脚点。2.3 栈帧递归背后的内存真相很多人不理解递归为什么“费内存”这里必须讲清楚栈帧的概念。每次函数调用系统都会在调用栈上开辟一块空间用来存放这个函数的参数、局部变量和返回地址这块空间就叫栈帧。递归调用一层就压一个栈帧返回一层就弹一个栈帧。汉诺塔如果盘子数是 n递归深度就是 n栈里最多同时存在 n 个栈帧。青蛙跳台阶的朴素递归更夸张它的调用次数是指数级增长的虽然栈深度只有 n但函数被调用的总次数是 2 的 n 次方级别。这就是为什么 n 稍微大一点程序就卡死或者直接崩掉。理解栈帧之后你就能明白两件事第一递归深度不能太深否则栈会溢出第二递归的调用次数直接决定性能能减少重复调用就要减少。这两点会贯穿后面所有的优化讨论。3. 汉诺塔递归思维的试金石3.1 问题描述与规则约束汉诺塔的设定很简洁有三根柱子假设叫 A、B、CA 柱上从下到上摞着 n 个大小不一的盘子大的在下小的在上。目标是把所有盘子从 A 柱移动到 C 柱移动过程中必须遵守两条规则每次只能移动一个盘子任何时候大盘子都不能压在小盘子上面。B 柱作为辅助柱可以临时存放盘子。这个问题的难点在于盘子一多手动去推演就完全乱了。三个盘子还好说四个盘子就开始头晕五个以上基本靠猜。但递归的妙处就在于它能把这种看似复杂的问题用几行代码就描述清楚。3.2 把大问题拆成同构的小问题递归思维的核心是问题分解。我们盯着最大的那个盘子看它最终一定要从 A 移到 C。但在移动它之前它上面的 n-1 个盘子必须先挪走而且不能压在它上面所以这 n-1 个盘子只能先挪到 B 柱上。等最大的盘子从 A 移到 C 之后再把 B 柱上的 n-1 个盘子挪到 C 柱上。关键来了把 n-1 个盘子从一根柱子挪到另一根柱子这不就是原问题规模缩小版吗只不过起点、终点、辅助柱换了一下而已。于是整个问题就变成了三步把 A 上的 n-1 个盘子借助 C移动到 B把 A 上剩下的最大盘子直接移动到 C把 B 上的 n-1 个盘子借助 A移动到 C。第一步和第三步都是原问题的子问题规模从 n 变成了 n-1。一直拆下去拆到只剩一个盘子的时候直接移动就行这就是递归出口。3.3 代码实现与逐行拆解public void hanoi(int n, char from, char aux, char to) { if (n 1) { System.out.println(移动盘子 n 从 from 到 to); return; } hanoi(n - 1, from, to, aux); System.out.println(移动盘子 n 从 from 到 to); hanoi(n - 1, aux, from, to); }这段代码短到可以背下来但每一行的参数顺序都有讲究。我逐个说。hanoi(n, from, aux, to)这四个参数的含义是把 n 个盘子从 from 柱借助 aux 柱移动到 to 柱。参数顺序不能乱因为递归调用时柱子的角色会互换。出口是n 1只剩一个盘子时直接移动不需要再借助任何柱子。第一个递归调用hanoi(n - 1, from, to, aux)意思是把上面 n-1 个盘子从 from 挪到 aux这时候 to 变成了辅助柱。为什么因为最大的盘子还压在 from 上最终要去 to所以这 n-1 个盘子不能去 to只能先去 aux 暂存。中间那行打印是把当前最大的盘子从 from 直接移到 to这一步是确定的不需要递归。第二个递归调用hanoi(n - 1, aux, from, to)意思是把暂存在 aux 上的 n-1 个盘子借助 from移动到 to。这时候 from 空了正好当辅助柱。提示写汉诺塔最容易搞混的就是递归调用里三个柱子的顺序。我的经验是先想清楚“我现在要把哪堆盘子、从哪、借助哪、移到哪”然后按这个顺序填参数不要死记硬背。3.4 移动次数与复杂度分析汉诺塔的移动次数有个精确的公式。设 n 个盘子需要 T(n) 次移动根据上面的三步分解可以列出递推式T(n) T(n-1) 1 T(n-1) 2T(n-1) 1其中 T(1) 1。把这个式子展开T(n) 2^n - 1。也就是说n 个盘子需要移动 2 的 n 次方减 1 次。这个数字增长得非常恐怖。n10 时需要 1023 次n20 时需要一百多万次n64 时需要大约 1.8 乘以 10 的 19 次方次。传说中那个 64 盘汉诺塔的寓言说完成之时世界末日就到了从计算量上看确实不是瞎编的。时间复杂度是 O(2^n)空间复杂度是 O(n)因为递归深度是 n栈里最多压 n 个栈帧。这个空间复杂度比时间复杂度温和得多所以汉诺塔的瓶颈在时间不在内存。4. 青蛙跳台阶从递归到动态规划的进化4.1 问题描述与初步建模青蛙跳台阶的问题是这样的一只青蛙一次可以跳 1 级台阶也可以跳 2 级台阶。问跳上 n 级台阶总共有多少种跳法。这个问题看起来和汉诺塔没关系但递归的思路是一样的把大问题拆成小问题。我们站在第 n 级台阶上往回看青蛙最后一步只有两种可能要么是从第 n-1 级跳 1 级上来的要么是从第 n-2 级跳 2 级上来的。所以跳到第 n 级的跳法数等于跳到第 n-1 级的跳法数加上跳到第 n-2 级的跳法数。用公式表示就是 f(n) f(n-1) f(n-2)。看到这个式子熟悉的人立刻会反应过来这不就是斐波那契数列吗没错青蛙跳台阶本质上就是斐波那契数列的一个变体只是初始条件略有不同。4.2 递归出口的确定递推式有了接下来定出口。青蛙跳 1 级台阶只有 1 种跳法就是一次跳 1 级所以 f(1) 1。跳 2 级台阶有两种跳法一次跳 2 级或者分两次各跳 1 级所以 f(2) 2。这两个出口必须写死否则递归没有终点。有些变体题目里青蛙可以跳 1 到 n 级那出口和递推式都会变但思路是一样的。4.3 朴素递归的代码与性能陷阱public int jump(int n) { if (n 1) return 1; if (n 2) return 2; return jump(n - 1) jump(n - 2); }这段代码逻辑完全正确写起来也简洁。但它有个致命问题大量重复计算。我画一下 n5 的调用过程你就明白了。算 jump(5) 需要 jump(4) 和 jump(3)算 jump(4) 需要 jump(3) 和 jump(2)算 jump(3) 需要 jump(2) 和 jump(1)。你会发现 jump(3) 被算了两遍jump(2) 被算了三遍。n 越大重复的次数越多整个调用次数呈指数级增长。实测一下n40 的时候朴素递归大概要跑几秒钟n45 的时候可能要几十秒n50 基本就等到天荒地老了。时间复杂度是 O(2^n)和汉诺塔一个级别。这就是为什么面试里问青蛙跳台阶面试官往往不是看你写不写得出来而是看你知不知道要优化。4.4 记忆化给递归加个缓存优化的第一步是记忆化也就是用一个数组或者哈希表把已经算过的结果存起来下次再需要就直接取不再重复计算。public int jump(int n, int[] memo) { if (n 1) return 1; if (n 2) return 2; if (memo[n] ! 0) return memo[n]; memo[n] jump(n - 1, memo) jump(n - 2, memo); return memo[n]; }调用前先初始化一个长度为 n1 的数组全部置 0。每次算出一个结果就存进 memo下次进来先查缓存。这样每个子问题只算一次时间复杂度直接降到 O(n)空间复杂度也是 O(n)因为要开数组递归栈深度也是 n。记忆化递归的好处是保留了递归的直观性代码结构和朴素递归几乎一样只是多了查缓存和存缓存两步。对于刚理解递归的人来说这是从朴素递归过渡到动态规划最自然的桥梁。4.5 迭代写法把递归改成循环记忆化虽然快但递归调用本身有开销而且 n 很大时栈深度可能溢出。更彻底的做法是改成迭代从底往上算。public int jump(int n) { if (n 1) return 1; if (n 2) return 2; int prev2 1; int prev1 2; int result 0; for (int i 3; i n; i) { result prev1 prev2; prev2 prev1; prev1 result; } return result; }这段代码用两个变量滚动保存前两个结果从 3 一直算到 n。时间复杂度 O(n)空间复杂度 O(1)因为只用了常数个变量。这是青蛙跳台阶的最优解法也是动态规划里“滚动数组”思想的典型应用。从朴素递归到记忆化再到迭代这条优化路径非常经典。它展示了一个通用思路先用递归把问题描述清楚再通过缓存消除重复计算最后用迭代消除递归开销。很多动态规划题目都可以按这个套路来。5. 两个问题的横向对比与深层联系5.1 递归结构上的异同汉诺塔和青蛙跳台阶虽然都是递归的经典案例但它们的递归结构差别很大放在一起对比能看清很多东西。对比维度汉诺塔青蛙跳台阶递归调用次数每次分解出 2 个子调用每次分解出 2 个子调用子问题是否重叠不重叠每个子问题独立大量重叠重复计算严重时间复杂度O(2^n)无法优化朴素 O(2^n)可优化到 O(n)空间复杂度O(n)递归深度朴素 O(n)迭代可到 O(1)优化空间几乎没有很大记忆化和迭代都能大幅提升本质分治思想动态规划思想最关键的区别在于子问题是否重叠。汉诺塔的每个子问题都是独立的算过的结果不会再用到所以没有优化余地2^n 次移动是理论下界。青蛙跳台阶的子问题大量重叠同一个 f(k) 会被反复计算所以缓存能带来质的飞跃。这个区别对应了算法里两个重要概念分治法和动态规划。分治法适用于子问题独立的情况动态规划适用于子问题重叠的情况。汉诺塔是分治的典型青蛙跳台阶是动态规划的入门。5.2 递归深度的实际影响两个问题的递归深度都是 n但实际影响不同。汉诺塔的 n 通常不会太大因为 2^n 的时间复杂度摆在那里n30 就已经是十亿次操作了实际能跑的 n 很小栈深度根本不是瓶颈。青蛙跳台阶的朴素递归虽然也慢但如果用记忆化或迭代n 可以取到很大比如 n1000 甚至更大这时候如果用递归写法栈深度就可能溢出。Java 默认的栈大小通常在 512KB 到 1MB 之间每层栈帧占几十到几百字节不等粗略估算递归深度大概在几千到一万层左右就会溢出。所以青蛙跳台阶如果非要用递归n 超过几千就要小心了。迭代写法没有这个问题可以放心用。注意不要因为递归代码简洁就无脑用递归。递归深度受栈大小限制处理大规模数据时迭代往往是更稳妥的选择。6. 实操中的常见坑与排查技巧6.1 递归出口写错的几种典型情况递归出口写错是最常见的 bug我整理了几种典型情况。第一种是漏写出口函数无限调用直接栈溢出。这种错误最明显报错信息里会有一长串重复的堆栈跟踪一眼就能看出来。第二种是出口条件写反比如把n 1写成n ! 1导致该停的时候不停不该停的时候停了。这种错误比较隐蔽程序可能不报错但结果完全不对。第三种是出口不完整比如青蛙跳台阶只写了n 1的出口没写n 2那 n2 时会继续往下调用 jump(1) 和 jump(0)jump(0) 又没定义结果就错了。出口必须覆盖所有最小规模的情况。第四种是出口位置放错把出口写在递归调用之后导致递归先执行了才判断出口等于没写。出口必须在递归调用之前判断。6.2 栈溢出的排查思路遇到StackOverflowError排查思路是这样的先看递归出口是否存在且正确。这是最常见的原因九成以上的栈溢出都是出口问题。如果出口没问题再看递归深度是否过大。可以打印一下递归层数或者在递归函数里加个计数器看看实际深度是多少。如果深度确实很大考虑改成迭代或者调整栈大小。调整栈大小可以用 JVM 参数-Xss比如-Xss4m把栈调到 4MB。但这只是权宜之计根本解法还是降低递归深度或者改迭代。还有一种情况是递归逻辑本身有问题导致递归方向不对比如该往 n 减小的方向递归结果写成了 n 增大那永远到不了出口。6.3 性能问题的定位方法青蛙跳台阶的朴素递归慢但慢在哪里需要定位。最简单的办法是加个计数器统计函数被调用了多少次。n30 的时候朴素递归的调用次数大概是几百万次而记忆化只有 30 次左右差距一目了然。也可以用时间戳测一下不同 n 的耗时画个曲线。朴素递归的耗时曲线是指数上升的记忆化和迭代是线性上升的。看到指数曲线基本就能确定是重复计算的问题。定位到问题之后优化方向就明确了加缓存消除重复计算或者改迭代消除递归开销。6.4 常见问题速查表问题现象可能原因排查方法解决方案StackOverflowError递归出口缺失或错误检查出口条件和位置补全或修正出口结果不正确出口条件写反或不完整手动推演小规模情况修正出口逻辑程序运行极慢重复计算严重加计数器统计调用次数记忆化或改迭代n 较大时崩溃递归深度超限打印递归深度改迭代或调大栈结果溢出为负数int 范围不够检查 n 的取值范围改用 long 或 BigInteger7. 从经典题目到真实应用7.1 递归在树形结构处理中的应用汉诺塔的递归思维在处理树形结构时天天都在用。比如遍历一棵二叉树前序、中序、后序遍历的代码结构和汉诺塔非常像先处理当前节点再递归处理左子树最后递归处理右子树。出口就是节点为空。public void preOrder(TreeNode node) { if (node null) return; System.out.println(node.val); preOrder(node.left); preOrder(node.right); }你看出口是node null递归调用两次分别处理左右子树。这个结构和汉诺塔的“分解成两个子问题”如出一辙。理解了汉诺塔理解树的递归遍历就轻松多了。7.2 动态规划思想的实际落地青蛙跳台阶背后的动态规划思想在实际项目里应用非常广。比如计算最短路径、背包问题、编辑距离、股票买卖的最佳时机本质上都是把大问题拆成子问题找到递推关系然后从底往上算或者加缓存。青蛙跳台阶是这些问题的简化版但它的优化路径——朴素递归、记忆化、迭代——是通用的。你把这套路径走通了遇到更复杂的动态规划问题思路是一样的先找递推式再定出口然后考虑要不要缓存最后看能不能改迭代省空间。7.3 递归思维的边界与取舍递归不是万能的它有明确的适用边界。适合用递归的场景是问题可以分解成同构的子问题子问题规模更小且有明确的出口。树形结构、分治算法、回溯搜索都属于这类。不适合用递归的场景是递归深度可能很大或者子问题重叠严重且没有缓存。前者会导致栈溢出后者会导致性能灾难。这两种情况下迭代或者动态规划是更好的选择。我个人的经验是写代码时先用递归把逻辑理清楚因为递归最贴近问题的自然描述。理清楚之后再评估性能和深度如果没问题就用递归有问题就改迭代。不要一上来就想着怎么优化先把问题解对再解好。8. 我踩过的那些坑最后分享几个我自己在写这两个题目时踩过的坑都是实打实的教训。第一个坑是汉诺塔的参数顺序。我刚开始学的时候总是把from、aux、to搞混代码写出来能跑但结果不对。后来我的办法是每次写递归调用之前先用中文把这句话念一遍“把 n-1 个盘子从 X 借助 Y 移到 Z”然后按念的顺序填参数就再也没错过。第二个坑是青蛙跳台阶的出口。我有一次只写了n 1的出口忘了n 2测试 n2 的时候结果不对查了半天才发现。后来我养成了一个习惯写完递归出口先把最小的几个情况手动代进去验算一遍确认没问题再往下写。第三个坑是性能。我第一次用朴素递归算青蛙跳台阶n 取到 45 的时候程序卡住了我还以为是死循环查了半天才发现是指数级重复计算。从那以后只要递归里出现两个以上的递归调用我都会下意识地想想有没有重复计算要不要加缓存。第四个坑是栈溢出。有一次处理一个深度很大的树递归遍历直接崩了报StackOverflowError。当时第一反应是调大栈但调大之后还是崩最后改成迭代才解决。这件事让我明白递归深度是有硬上限的不能指望调参数解决所有问题。这些坑说起来都是小事但真踩进去的时候每一个都能耗掉你半天时间。希望你看完之后能少走点弯路。递归这个东西理解了原理之后剩下的就是多写多练把那些边界情况和性能陷阱变成肌肉记忆。汉诺塔和青蛙跳台阶虽然简单但它们是通往更复杂算法的敲门砖把这两块砖踩实了后面的路会好走很多。
阅读完成 · 觉得有帮助？
