★ FEATURED ARTICLE 1. 从两个老生常谈的递归题说起汉诺塔和青蛙跳台阶几乎是每一本数据结构与算法教材里绕不开的两个递归入门案例。很多人第一次接触递归这个概念就是从这两道题开始的。但有意思的是我面试过不少工作两三年的Java开发让他们手写一个汉诺塔的递归解法能写出来的人不到一半再追问一句青蛙跳台阶的递归和汉诺塔的递归本质区别在哪能说清楚的人就更少了。这不是因为题目难而是因为大多数人在学习阶段只是看懂了答案并没有真正把递归的思维方式内化成自己的东西。看懂和会写之间隔着一条很深的鸿沟。看懂是跟着别人的思路走一遍觉得哦原来是这样会写是你面对一个全新的问题能自己判断它能不能用递归、递归的边界在哪、递推关系怎么找。这篇文章我打算把这两道题彻底拆开讲透。不只是给出代码而是把递归的思维过程完整地展示出来——遇到一个问题我是怎么判断它适合递归的怎么找到递推公式的怎么确定终止条件的以及在实际写代码时容易踩哪些坑。文章会涉及Java代码实现、递归调用栈的底层分析、时间复杂度推导、以及从递归到迭代的优化思路。无论你是刚学递归的新手还是想重新梳理一下基础的老手应该都能从中找到有价值的东西。2. 递归思维的本质自己调用自己到底在做什么2.1 递归不是循环别把它们混为一谈很多人初学递归时会下意识地把递归理解成一种特殊的循环。这个理解不能说完全错但它会严重阻碍你真正掌握递归。循环是线性的——你从第一个元素开始处理完跳到第二个再跳到第三个一路平推过去。递归是树状的——你把一个大问题拆成若干个小问题每个小问题再拆成更小的问题直到小到可以直接解决。这个拆解过程在调用栈上展开形成一棵调用树。举个生活中的例子。循环就像你爬楼梯一层一层往上走每一步都是重复的动作。递归更像俄罗斯套娃——你打开最外面那个娃娃发现里面还有一个一模一样的但更小的娃娃你继续打开直到最里面那个小到不能再打开为止然后你再一层一层把娃娃合回去。这个打开的过程叫递推合回去的过程叫回归。递归之所以叫递归就是因为它同时包含递推和回归两个阶段。很多人写递归只想着怎么往下拆忘了还要往上合结果代码就写残了。2.2 递归的两个必要条件终止条件和递推关系任何一个正确的递归函数必须同时满足两个条件终止条件Base Case什么时候停止递归直接返回结果。没有终止条件的递归会无限调用下去最终导致栈溢出StackOverflowError。这是Java中最常见的递归错误。递推关系Recurrence Relation大问题如何拆解为小问题小问题的解如何组合成大问题的解。这是递归的核心逻辑也是最能体现思维水平的地方。用数学语言表达就是f(n) g(f(n-1), f(n-2), ...)其中g是某种组合方式。找到这个g递归就写出来了一半。我个人的经验是写递归的时候不要试图在脑子里模拟整个调用过程——人脑的栈深度非常有限超过三层你就晕了。正确的做法是信任递归假设f(n-1)已经正确解决了你只需要考虑怎么用f(n-1)的结果来解决f(n)。这种思维方式叫做递归信任或者递归跳跃。2.3 调用栈递归背后的内存模型每次递归调用JVM都会在调用栈上压入一个新的栈帧Stack Frame。栈帧里保存了当前方法的局部变量、参数、返回地址等信息。当递归深度过大时栈帧数量超过JVM允许的最大深度就会抛出StackOverflowError。Java默认的栈大小通常是512KB到1MB取决于JVM版本和操作系统可以通过-Xss参数调整。以每个栈帧约100字节估算默认情况下递归深度大概在几千到一万层左右。汉诺塔n30时递归深度是30完全没问题但如果n100000递归深度就是100000必然栈溢出。理解调用栈对调试递归非常重要。当递归结果不对时最有效的调试方式不是打断点一步步跟调用树太大根本跟不过来而是在递归函数的入口打印当前参数观察调用顺序是否符合预期。3. 汉诺塔递归拆解的教科书级案例3.1 问题描述与规则约束汉诺塔的问题描述很简洁有三根柱子记为A、B、CA柱上从下到上叠着n个大小递减的圆盘。要求把所有圆盘从A柱移动到C柱移动过程中必须遵守三条规则每次只能移动一个圆盘圆盘只能放在柱子上不能悬空任何时候大盘都不能压在小盘上面B柱作为辅助柱使用。问最少需要多少步移动的过程是怎样的这个问题看起来简单但手动模拟n4以上就会开始混乱。而递归解法只需要不到十行代码这就是递归的威力——它让你不需要关心每一步具体怎么走只需要关心问题的结构。3.2 从n1到n3的手动推演在写代码之前先手动推演几个小规模的情况这有助于建立直觉。n1的情况只有一个盘子直接从A移到C。1步。n2的情况先把小盘从A移到B再把大盘从A移到C最后把小盘从B移到C。3步。n3的情况这里开始有意思了。我们的目标是把最大的盘第3个盘从A移到C。但最大的盘上面压着两个小盘必须先想办法把这两个小盘挪走。挪到哪里不能挪到C因为C要留给最大的盘。所以只能挪到B。于是问题分解为第一步把上面2个盘从A移到B借助C第二步把最大的盘从A移到C第三步把B上的2个盘移到C借助A注意第一步和第三步都是把2个盘从一根柱子移到另一根柱子的问题这正是n2的子问题。所以n3的解法里嵌套了n2的解法。3.3 递推关系的推导过程把上面的推演推广到任意n要把n个盘从A移到C借助B先把上面n-1个盘从A移到B借助C——这是一个规模为n-1的子问题把最底下的第n个盘从A移到C——这是一步直接操作把B上的n-1个盘移到C借助A——这又是一个规模为n-1的子问题用函数签名表示hanoi(n, from, to, aux)表示把n个盘从from柱借助aux柱移到to柱。递推关系就是hanoi(n, from, to, aux): hanoi(n-1, from, aux, to) // 把n-1个盘从from移到aux借助to move(from, to) // 把第n个盘从from移到to hanoi(n-1, aux, to, from) // 把n-1个盘从aux移到to借助from终止条件n1时直接move(from, to)不再递归。这里的关键洞察是柱子的角色是相对的。在第一步中B是目标柱在第三步中B是源柱。同一个柱子在不同阶段扮演不同角色这就是为什么函数需要三个柱子参数而不是硬编码。3.4 Java代码实现与逐行注释public class HanoiTower { private static int stepCount 0; /** * 汉诺塔递归解法 * param n 待移动的圆盘数量 * param from 源柱 * param to 目标柱 * param aux 辅助柱 */ public static void hanoi(int n, char from, char to, char aux) { // 终止条件只剩一个盘时直接移动 if (n 1) { stepCount; System.out.println(第 stepCount 步: from - to); return; } // 第一步把上面n-1个盘从from移到aux借助to hanoi(n - 1, from, aux, to); // 第二步把最底下的第n个盘从from移到to stepCount; System.out.println(第 stepCount 步: from - to); // 第三步把aux上的n-1个盘移到to借助from hanoi(n - 1, aux, to, from); } public static void main(String[] args) { int n 3; System.out.println(汉诺塔 n n 的移动过程); hanoi(n, A, C, B); System.out.println(总共需要 stepCount 步); } }运行n3的输出第1步: A - C 第2步: A - B 第3步: C - B 第4步: A - C 第5步: B - A 第6步: B - C 第7步: A - C 总共需要 7 步你可以手动验证一下这7步是否满足所有规则。我建议你拿三枚大小不同的硬币实际摆一下跟着输出走一遍。这个动手过程对建立递归直觉非常有帮助比盯着代码看十分钟都管用。3.5 时间复杂度为什么是2的n次方减1设T(n)为移动n个盘所需的步数。根据递推关系T(n) T(n-1) 1 T(n-1) 2T(n-1) 1展开这个递推式T(n) 2T(n-1) 1T(n-1) 2T(n-2) 1...T(1) 1逐层代入 T(n) 2(2T(n-2) 1) 1 4T(n-2) 3 4(2T(n-3) 1) 3 8T(n-3) 7 ...规律很明显T(n) 2^k * T(n-k) (2^k - 1)当k n-1时T(n) 2^(n-1) * T(1) (2^(n-1) - 1) 2^(n-1) 2^(n-1) - 1 2^n - 1所以时间复杂度是O(2^n)。这是一个指数级算法。n64时步数是2^64-1约等于1.8×10^19步。即使每秒移动一亿步也需要将近六千年。这就是为什么汉诺塔常被用来演示指数爆炸的威力。空间复杂度是O(n)因为递归调用栈的最大深度是n。3.6 一个容易忽略的细节参数顺序的陷阱写汉诺塔递归时最容易出错的地方是递归调用时的参数顺序。特别是第三步hanoi(n-1, aux, to, from)很多人会写成hanoi(n-1, aux, from, to)。区别在哪第三步的目标是把盘从aux移到to借助from。所以第二个参数源是aux第三个参数目标是to第四个参数辅助是from。如果你把from和to的位置搞反了程序不会报错但输出结果是错的——盘子会移来移去但最终到不了C柱。我的建议是写递归调用时在脑子里默念从哪来、到哪去、借助谁然后按这个顺序填参数。不要凭记忆写要凭逻辑写。4. 青蛙跳台阶递推关系的另一种形态4.1 问题描述与初步分析青蛙跳台阶的问题一只青蛙一次可以跳1级台阶也可以跳2级台阶。问跳上n级台阶总共有多少种跳法这个问题和汉诺塔看起来都是递归但它们的递归结构完全不同。汉诺塔的递归是把问题拆成两个子问题加一步操作青蛙跳台阶的递归是最后一步的选择决定了前面的子问题。先手动算几个小规模的情况建立直觉n1只有1种跳法跳1级n2有2种跳法11 或 直接跳2级n3有3种跳法111、12、21n4有5种跳法1111、112、121、211、22n5有8种跳法序列是1, 2, 3, 5, 8, ... 眼熟吗这就是斐波那契数列。事实上青蛙跳台阶就是斐波那契数列的一个变体。4.2 逆向思维从最后一步倒推正向思考第一步跳1级还是2级会导致分支越来越多很难理清。正确的思路是逆向思考考虑最后一步。要跳到第n级台阶最后一步只有两种可能最后一步跳了1级那么之前必须已经跳到了第n-1级最后一步跳了2级那么之前必须已经跳到了第n-2级所以跳到第n级的跳法数 跳到第n-1级的跳法数 跳到第n-2级的跳法数。用公式表示f(n) f(n-1) f(n-2)终止条件f(1) 1f(2) 2这就是完整的递推关系。是不是比汉诺塔简单多了但简单不代表没有坑后面会讲到几个常见的错误。4.3 递归实现与性能问题public class FrogJump { /** * 递归解法青蛙跳台阶 * 时间复杂度 O(2^n)存在大量重复计算 */ public static int jumpRecursive(int n) { if (n 0) { throw new IllegalArgumentException(台阶数必须大于0); } if (n 1) return 1; if (n 2) return 2; return jumpRecursive(n - 1) jumpRecursive(n - 2); } public static void main(String[] args) { for (int i 1; i 10; i) { System.out.println(跳 i 级台阶有 jumpRecursive(i) 种跳法); } } }这段代码逻辑上完全正确但性能极差。为什么因为存在大量的重复计算。以f(5)为例调用树是这样的f(5) ├── f(4) │ ├── f(3) │ │ ├── f(2) │ │ └── f(1) │ └── f(2) └── f(3) ├── f(2) └── f(1)可以看到f(3)被计算了2次f(2)被计算了3次。随着n增大重复计算的规模呈指数级增长。n40时程序会卡住好几秒n50时基本就跑不出来了。4.4 记忆化搜索用空间换时间解决重复计算最直接的办法是加一个缓存备忘录。每次计算f(n)之前先查缓存如果算过了就直接返回没算过就算完存进去。import java.util.HashMap; import java.util.Map; public class FrogJumpMemo { private static MapInteger, Integer memo new HashMap(); public static int jumpMemo(int n) { if (n 0) { throw new IllegalArgumentException(台阶数必须大于0); } if (n 1) return 1; if (n 2) return 2; // 查缓存 if (memo.containsKey(n)) { return memo.get(n); } // 计算并存入缓存 int result jumpMemo(n - 1) jumpMemo(n - 2); memo.put(n, result); return result; } public static void main(String[] args) { System.out.println(跳40级台阶有 jumpMemo(40) 种跳法); // 输出跳40级台阶有 165580141 种跳法 } }加了记忆化之后每个f(n)只计算一次时间复杂度从O(2^n)降到O(n)空间复杂度是O(n)缓存加递归栈。n40瞬间就能出结果。这种递归缓存的思路就是动态规划的自顶向下写法。它保留了递归的直观性同时消除了重复计算。我个人在实际工作中遇到递归性能问题时第一反应就是加记忆化往往几行代码就能把指数级降到线性级。4.5 迭代解法从递归到循环的转换记忆化虽然好但递归调用本身有栈开销。如果n非常大比如n10000递归深度太大会栈溢出。这时候就需要把递归改成迭代。观察递推关系f(n) f(n-1) f(n-2)这本质上就是一个斐波那契数列。我们可以用两个变量滚动向前计算public class FrogJumpIterative { /** * 迭代解法时间复杂度 O(n)空间复杂度 O(1) */ public static long jumpIterative(int n) { if (n 0) { throw new IllegalArgumentException(台阶数必须大于0); } if (n 1) return 1; if (n 2) return 2; long prev2 1; // f(1) long prev1 2; // f(2) long current 0; for (int i 3; i n; i) { current prev1 prev2; prev2 prev1; prev1 current; } return current; } public static void main(String[] args) { System.out.println(跳50级台阶有 jumpIterative(50) 种跳法); // 输出跳50级台阶有 20365011074 种跳法 } }注意这里返回值类型改成了long因为n50时结果已经超过了int的最大值约21亿。n46时结果是2971215073已经溢出了int范围。这是一个非常容易踩的坑——用int存储结果n稍微大一点就变成负数了。迭代版本的空间复杂度是O(1)只用了三个变量。时间复杂度和记忆化版本一样是O(n)但没有递归栈开销n100000也能秒出结果。4.6 青蛙跳台阶的变体一次可以跳1到m级原题是青蛙一次可以跳1级或2级。如果改成一次可以跳1级、2级、...、m级呢这时候递推关系变成f(n) f(n-1) f(n-2) ... f(n-m)终止条件需要仔细处理当n m时f(n) 2^(n-1)。因为对于前n级台阶每一步都可以选择跳或不跳最后一步必须跳所以有2^(n-1)种跳法。这个变体的代码实现稍微复杂一些但核心思路不变——找到最后一步的所有可能性把问题拆解为子问题。有兴趣的读者可以自己尝试实现一下作为对递归思维的进一步练习。5. 两道题背后的递归设计模式对比5.1 问题拆解方式的根本差异汉诺塔和青蛙跳台阶虽然都是递归但它们的拆解逻辑有本质区别。汉诺塔是分治型递归把问题拆成两个规模为n-1的独立子问题外加一步直接操作。两个子问题之间没有重叠各自独立求解。这种递归的调用树是一棵满二叉树节点数就是总步数。青蛙跳台阶是递推型递归f(n)依赖于f(n-1)和f(n-2)子问题之间存在重叠。这种递归的调用树不是树状展开的而是有大量共享节点。正因为有重叠才需要记忆化来优化。用一句话概括分治型递归的子问题互不重叠递推型递归的子问题存在重叠。前者不需要缓存后者需要。5.2 终止条件的设置技巧汉诺塔的终止条件是n1因为一个盘不需要拆解直接移动即可。青蛙跳台阶的终止条件是n1和n2因为这两个规模的问题无法再拆解n1时只能跳1级n2时有两种跳法。设置终止条件的原则是最小规模的、可以直接给出答案的情况。终止条件设得太多代码冗余设得太少递归无法收敛。一个常见的错误是终止条件写错导致无限递归。比如青蛙跳台阶如果只写if (n 1) return 1;而忘了n2的情况那么f(2)会调用f(1)和f(0)f(0)又会调用f(-1)和f(-2)一路负下去直到栈溢出。5.3 递归深度与栈溢出的实际测试我实际测试过Java默认配置下的递归深度极限。写一个简单的递归函数每次n减1看n到多少时抛StackOverflowErrorpublic class StackDepthTest { static int depth 0; public static void recurse(int n) { depth; recurse(n - 1); } public static void main(String[] args) { try { recurse(1000000); } catch (StackOverflowError e) { System.out.println(最大递归深度: depth); } } }在我的机器上JDK 17默认栈大小最大深度大约在10000到12000之间。这意味着如果n超过这个数量级递归解法就会崩溃。青蛙跳台阶的迭代解法没有这个问题汉诺塔的递归深度是nn通常不会太大所以一般不需要担心。但如果确实需要更深的递归可以通过-Xss参数增大栈大小。比如java -Xss10m可以把栈大小设为10MB递归深度能到十万级别。不过这只是权宜之计根本的解决办法还是把递归改成迭代。6. 递归代码的调试与常见错误排查6.1 递归结果不对时怎么定位问题递归代码出bug时最忌讳的就是在IDE里一步步单步调试。调用树稍微大一点你根本跟不过来而且很容易迷失在层层返回中。我的做法是打印调用日志。在递归函数入口打印当前参数和深度出口打印返回值。这样你能看到完整的调用序列一眼就能发现哪里不对。public static int jumpDebug(int n, int depth) { String indent .repeat(depth); System.out.println(indent 进入 f( n )); if (n 1) { System.out.println(indent 返回 f(1)1); return 1; } if (n 2) { System.out.println(indent 返回 f(2)2); return 2; } int result jumpDebug(n - 1, depth 1) jumpDebug(n - 2, depth 1); System.out.println(indent 返回 f( n ) result); return result; }运行jumpDebug(4, 0)输出会清晰地展示整个调用树。如果某个分支的返回值不对你能立刻定位到是哪一层出了问题。6.2 三个高频错误及修复方案错误一终止条件遗漏或写错。这是最常见的错误表现为StackOverflowError。修复方法是仔细检查终止条件是否覆盖了所有最小规模的情况。错误二递归调用参数顺序错误。汉诺塔中特别容易犯表现为结果不对但不报错。修复方法是每次写递归调用时对照函数签名逐个确认参数含义。错误三返回值类型溢出。青蛙跳台阶n较大时int装不下结果。修复方法是改用long或者用BigInteger处理更大的数。6.3 用IDE的调用栈视图辅助分析虽然不建议单步调试递归但IDE的调用栈视图Call Stack在递归报错时非常有用。当StackOverflowError抛出时IDE会显示完整的调用栈你能看到递归是在哪一层开始失控的。在IntelliJ IDEA中异常抛出时点击调用栈中的任意一帧可以查看该帧的局部变量值。这对于定位哪一层开始参数不对非常高效。7. 从递归到动态规划的进阶思路7.1 什么情况下递归需要优化判断标准很简单如果递归调用树中存在重复的子问题就需要优化。汉诺塔的子问题不重复所以不需要优化O(2^n)就是它的真实复杂度无法改进。青蛙跳台阶的子问题大量重复所以需要优化。优化手段有两种记忆化自顶向下和迭代自底向上。7.2 记忆化搜索的通用模板记忆化搜索有一个通用模板适用于大多数递推型递归问题public class MemoTemplate { private MapInteger, Long memo new HashMap(); public long solve(int n) { // 1. 查缓存 if (memo.containsKey(n)) { return memo.get(n); } // 2. 终止条件 if (n 1) return 1; if (n 2) return 2; // 3. 递推计算 long result solve(n - 1) solve(n - 2); // 4. 存缓存 memo.put(n, result); return result; } }这个模板可以套用到任何形如f(n) g(f(n-1), f(n-2), ...)的问题上。把终止条件和递推公式替换掉就行。7.3 迭代版本的推导方法从递归到迭代的转换核心是找到计算的顺序。递归是自顶向下从n推到1迭代是自底向上从1推到n。具体做法确定需要保存多少个历史状态。青蛙跳台阶只需要前两个状态所以用两个变量。从最小的已知状态开始逐步向前计算。每次计算后更新历史状态变量。如果递推关系依赖前k个状态就需要k个变量或者一个长度为k的数组。比如f(n) f(n-1) f(n-2) f(n-3)就需要三个变量滚动。7.4 实际面试中怎么回答这类题面试中遇到汉诺塔或青蛙跳台阶面试官考察的绝对不只是你能不能写出代码。他们更关注的是你能不能清晰地描述递推关系是怎么推导出来的你知不知道递归的性能问题以及如何优化你能不能分析时间复杂度和空间复杂度你写代码时是否考虑了边界条件和溢出问题我的建议是先用手动推演小规模情况来展示思路然后写出递归解法接着主动指出性能问题并给出优化方案最后分析复杂度。这个流程走下来即使代码有小瑕疵面试官也会认可你的思维深度。8. 我在实际教学和面试中积累的几点体会教别人写递归这么多年我发现一个规律能写好递归的人往往不是最聪明的而是最愿意动手画图的人。汉诺塔这道题我见过太多人盯着代码看半天看不懂但拿几枚硬币摆弄五分钟就恍然大悟了。递归是空间思维光靠阅读代码很难建立直觉必须动手模拟。青蛙跳台阶这道题最大的价值不在于它本身而在于它是理解动态规划的绝佳入口。很多人学动态规划觉得难就是因为跳过了递归这一步直接去背状态转移方程。但如果你先把递归写出来再观察哪些子问题被重复计算了然后加缓存最后改成迭代——这个渐进的过程会让你真正理解动态规划在做什么而不是死记硬背。还有一个体会是关于代码风格的。写递归函数时我习惯把终止条件放在最前面递推逻辑放在后面。这样代码读起来清晰也不容易漏掉终止条件。另外递归函数的参数命名要能自解释比如from、to、aux就比a、b、c好得多。这些细节看似小事但在排查问题时能省很多时间。最后分享一个我常用的练习方法每学一个新的递归问题先手动推演n1到n5的结果列成表格观察规律尝试写出递推公式然后再写代码验证。这个先数学后代码的习惯能让你从被动地看懂答案变成主动地推导答案这才是真正掌握递归的标志。
阅读完成 · 觉得有帮助？
