如果你刷过算法题大概会有一种感觉递推和递归这两个词翻书、看视频都懂题目稍微变形就卡壳。尤其是遇到“第三项等于前两项之和”这类递推式上课明明听懂了斐波那契自己做爬楼梯、铺地砖、跳台阶又是一脸茫然。再看递归代码不过是一个函数自己调用自己但为什么有的递归几十层就栈溢出有的递归算到 n50 还没出结果有的递归明明逻辑没问题却一直死循环问题通常不出在“不懂定义”而出在缺少一条完整的学习路径没有把数列规律抽象成递推公式没有把递推公式翻译成递归程序也没有想清楚递推和递归之间到底怎么相互转换。我见过一类很早年的算法教材书名多半带着“数列”“递推”“递归”这样的字样。它们版面朴素、印量不大后来不少没有再版但很多高校老师至今仍把它当内部讲义用。这类老书的核心价值不是给你几百道题而是用很少的篇幅把一条主线讲透从观察数列到建立递推式再到用递归程序实现最后用递推或动态规划优化。本文就按照这条主线把递推与递归从数学到代码完整拆开。1. 递推与递归难在哪先找到真正的学习顺序很多人的学习顺序是反的。上来就写递归代码背一个“递归 自己调用自己 终止条件”然后开始刷题。这样能应付简单题但理解很浅一旦题目换皮就失效。老教材通常不会一上来就写程序。它们会先花不少篇幅讨论数列给出一串数让你观察相邻项的关系写成递推公式再让你从递推公式反推某一项最后才把递推公式搬进程序里。这个顺序背后有一个重要判断递推公式是数学模型递归程序是执行方式。真正决定题目能不能做出来的是你能不能先找到前一项与后一项的数量关系。递推与递归难难在它们不是两种孤立的技巧而是同一条思路的两端数学端递推式。用前项定义后项。程序端递归函数。用函数调用表达这种“自己依赖自己”的结构。递推法通常是正向推导。已知 f(1)、f(2)用循环从前往后推出 f(n)。递归法是从目标出发先把 f(n) 拆成 f(n-1) 和 f(n-2)一路拆到不能再拆的边界再一层一层把结果带回来。这两种方式只是方向不同底层的递推式可以是同一个。如果能看到这一层递推递归题就不再是一个个孤立的解法而是同一类“状态转移问题”的两种实现策略。本文后面会沿着几条经典问题线展开斐波那契数列、整数转字符串、汉诺塔。每一条都同时用递推和递归两个视角去看最终落到可以运行的代码上。2. 从数列开始为什么“递推式”是一切的入口老书讲递推几乎都是从数列观察开始的。比如下面这串数1, 1, 2, 3, 5, 8, 13, 21, ...肉眼能看出规律从第 3 项开始每一项等于前两项之和。用数学语言写就是F(1) 1 F(2) 1 F(n) F(n - 1) F(n - 2), n 3这个式子就叫递推公式也叫递推关系。它由两部分组成初值或边界条件F(1)、F(2)。递推规则F(n) 如何由前面若干项组合得到。缺少其中任何一个递推式都不完整。只有规则没有初值程序不知道从哪里开始只有初值没有规则后面的项推不出来。很多初学者常犯的错误是把 F(n)F(n-1)F(n-2) 当成“公式”死记却忽略了它的本质是“第 n 项与前面若干项之间的约束关系”。一旦题目换成爬楼梯一个人每次可以走 1 级或 2 级台阶问走到第 n 级有多少种走法。你能不能看出它和斐波那契是同一个递推式可以这样想走到第 n 级最后一步要么从第 n-1 级跨 1 级上来要么从第 n-2 级跨 2 级上来。所以走到第 n 级的方法数等于走到第 n-1 级的方法数加上走到第 n-2 级的方法数。设 f(n) 是走到第 n 级的方法数则f(1) 1 f(2) 2 f(n) f(n - 1) f(n - 2), n 3初值不同递推结构相同。这就是为什么光背斐波那契没有用关键是要训练“把问题状态转成递推式”的建模能力。老书强调“递推式是第一等公民”还有一层原因它把一个大问题压缩成一条短式子写代码前先写递推式相当于先画好地图再出发。后面所有的递归、递推、记忆化都是围绕这张地图展开的。3. 递归到底是什么一次“先深入再回溯”的旅行递归的教科书定义是函数直接或间接调用自身。这个定义没错但它只描述了表面动作没有解释递归为什么能解决问题。更准确的理解是递归是一种“规模降解”的执行策略。我们想解决规模为 n 的问题但暂时不直接解决而是把它改写成规模更小的同类问题。比如F(n) F(n - 1) F(n - 2)要求 F(5)先求 F(4) 和 F(3)要求 F(4)先求 F(3) 和 F(2)一路拆到 F(1)、F(2)。这两个值是已知边界直接返回。返回的过程再一层层把子结果相加最终得到 F(5)。如果把 F(5) 的调用过程画出来是这样的F(5) ├── F(4) │ ├── F(3) │ │ ├── F(2) │ │ └── F(1) │ └── F(2) └── F(3) ├── F(2) └── F(1)注意观察调用过程是一路向下深入不断拆解返回过程则是一路向上回溯不断合并结果。整个过程符合“先入后出”的顺序所以它依赖系统调用栈来保存每一层的现场。每次进入一个新的递归调用系统会为这次调用分配一块栈帧用来保存参数、局部变量和返回地址。递归返回后栈帧被弹出回到上一层继续执行。因此看递归代码时只盯着“自己调用自己”是不够的还要回答清楚三个问题边界是什么递归到什么时候停止。递归参数如何向边界靠近即每一层调用相比上一层问题规模是否在缩小。返回后做什么子结果如何组合成父结果。3.1 递归出口不是“可有可无的 if”而是递推式中的初值从数学角度说递推式包含初值从程序角度说递归函数必须包含终止条件。二者是对应的。初值对应递归出口递推规则对应递归调用。看下面这个错误代码public static long fibRec(int n) { return fibRec(n - 1) fibRec(n - 2); }没有终止条件函数会无限调用下去直到系统栈耗尽抛出 StackOverflowError。补上出口之后才完整public static long fibRec(int n) { if (n 1 || n 2) { return 1; } return fibRec(n - 1) fibRec(n - 2); }这个场景非常适合解释递归问题的排查思路当递归代码出现栈溢出时第一反应不应该是“递归层数太多”而是先检查递归出口是否缺失或者递归参数是否真的在向出口靠近。3.2 递归为何无处不在从算法题到真实系统递归不只是竞赛题和面试题里的技巧。它在真实系统里几乎随处可见文件系统遍历统计目录大小、删除目录、批量改文件名本质都是递归遍历树结构。版本管理工具例如 SVN 设置忽略目录时带有 -R 参数表示递归应用到所有子目录。编译原理表达式解析常用递归下降法。约束满足问题CSP八皇后、数独等搜索求解通常通过递归回溯实现。数据处理合并配置、展开树状菜单、生成目录树同样是递归。这意味着递归是程序员绕不开的基本功。只把它当面试题来准备容易错过它在工程里真正发挥作用的地方。4. 递推与递归如何相互转换同一个递推式既可以用递归实现也可以用循环递推实现。理解两者的转换是系统掌握的关键。4.1 从递归到递推把“自顶向下”改成“自底向上”递归是从 f(n) 出发不断下探到 f(1)、f(2)再把结果带回来。递推则反其道而行之我先算 f(1)、f(2)再算 f(3)一步一步推到 f(n)。本质是方向相反但使用的递推式完全一样。用 Python 的经典爬楼梯问题来对比更清晰# 递归写法自顶向下 def climb_rec(n): if n 1: return 1 if n 2: return 2 return climb_rec(n - 1) climb_rec(n - 2) # 递推写法自底向上 def climb_iter(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在很多语言里循环递推执行效率更高因为它省去了函数调用和栈帧分配的开销。更重要的是它没有递归深度限制不会因为 n 太大而栈溢出。4.2 从递推到递归把问题拆成“更小但同构”的问题反过来如果你已经写好了递推循环想改成递归版本思路是每一层递归只处理当前规模遇到规模更小的同类子问题就调用自己。以“递归法将一个整数 n 转换成字符串”这个经典题为例。题目的意思是不能直接依赖现成的字符串转换函数而要用递归拆解数字各位。假设输入是 12345我们希望输出字符串 12345。关键观察一个多位数 n 的十进制表示等于“去掉个位后的部分”的字符串再接上“个位数字”的字符。比如 12345可以拆成 1234 和 5而 1234 又可以拆成 123 和 4。这就是递归关系。递归出口是 n 只剩下一位时直接把这位数字转成字符返回。public class IntToString { public static String intToStr(long n) { if (n 0) { return 0; } if (n 0) { return - intToStr(-n); } if (n 10) { return String.valueOf(n); } return intToStr(n / 10) (char) (0 n % 10); } public static void main(String[] args) { System.out.println(intToStr(12345)); System.out.println(intToStr(0)); System.out.println(intToStr(-678)); System.out.println(intToStr(Long.MAX_VALUE)); } }调用过程如下intToStr(12345) → intToStr(1234) 5 → intToStr(123) 4 → intToStr(12) 3 → intToStr(1) 2 → 返回 1 → 返回 12 → 返回 123 → 返回 1234 → 返回 12345这段代码能处理负数和 0是因为递归入口已经做了负号处理和 n0 判断。如果题目限定输入为正整数递归部分还可以更短public static String positiveToStr(long n) { if (n 10) { return String.valueOf(n); } return positiveToStr(n / 10) (char) (0 n % 10); }这个例子很适合检验自己是否真的理解递归。因为它没有任何“高级数学”只有“拆数字 拼接字符串”但想做对仍要注意递归出口n 10 时直接返回否则会无限循环。拼接顺序整数转字符串时高位的递归调用先返回所以拼接时要把高位结果放在前面。负数处理如果不处理负数递归会永远执行 n 0 状态下除以 10逻辑混乱。4.3 递推与递归的对比表对比维度数学递推公式递推法循环递归法本质状态之间前后依赖的关系由初值向目标方向正向计算由目标方向边界拆解再回溯合并编程形态数学表达式for/while 循环函数调用自身依赖初值必须给出必须从初值开始迭代必须有递归出口即对应初值典型示例F(n)F(n-1)F(n-2)for 循环滚动更新变量函数递归调用优势简洁、可推导性能高、无栈溢出风险代码结构与数学定义一致风险不等同于可执行程序建模不直观深度过大会栈溢出可能重复计算这张表值得反复看。老书的学习逻辑是先理解数学递推公式再分别用循环和递归去翻译它。一旦你能熟练地在两种翻译之间切换递推和递归的“隔阂感”就会消失。5. 完整示例斐波那契数列的三种写法我们以斐波那契数列为核心把“递归、记忆化、递推循环”三种方案全部实现一遍。这是递推递归学习中最重要的一个综合练习。5.1 方案一朴素递归先写一个最简单、最贴近数学定义的版本// 文件路径com/example/recursion/FibonacciRec.java public class FibonacciRec { public static long fib(int n) { if (n 0) { throw new IllegalArgumentException(n 必须是正整数); } // 递归出口对应数学递推式 F(1)1, F(2)1 if (n 1 || n 2) { return 1; } // 递推规则F(n) F(n-1) F(n-2) return fib(n - 1) fib(n - 2); } public static void main(String[] args) { for (int i 1; i 10; i) { System.out.println(F( i ) fib(i)); } } }运行后输出F(1) 1 F(2) 1 F(3) 2 F(4) 3 F(5) 5 F(6) 8 F(7) 13 F(8) 21 F(9) 34 F(10) 55注意朴素递归的致命问题重复计算。计算 fib(5) 时fib(3) 会被计算两次计算 fib(6) 时fib(4) 会被重复计算多次。随着 n 增大调用次数呈指数级膨胀。实测时你可以尝试计算 fib(45)会发现程序明显变慢。这不是因为你的电脑不够好而是算法的复杂度达到了 O(2^n)。5.2 方案二记忆化递归既然重复计算是瓶颈可以用一个缓存数组把已经算过的结果存起来。下次遇到同样参数直接读取缓存// 文件路径com/example/recursion/FibonacciMemo.java public class FibonacciMemo { public static long fib(int n) { if (n 0) { throw new IllegalArgumentException(n 必须是正整数); } Long[] memo new Long[n 1]; return helper(n, memo); } private static long helper(int n, Long[] memo) { if (n 1 || n 2) { return 1; } // 已经计算过直接返回 if (memo[n] ! null) { return memo[n]; } memo[n] helper(n - 1, memo) helper(n - 2, memo); return memo[n]; } public static void main(String[] args) { for (int i 1; i 30; i) { System.out.println(F( i ) fib(i)); } } }记忆化后每个 n 最多计算一次时间复杂度降到 O(n)空间复杂度 O(n)。这个思路也是动态规划的雏形用额外空间记录子问题答案避免重复求解。在 Java 里这里使用 Long[] 而不是 long[]是因为需要区分“还没计算”和“结果是 0”。对于斐波那契数列正常结果不会为 0用 long[] 也可以但 Long[] 表示更严谨语义更清晰。5.3 方案三递推循环如果追求最低空间开销可以直接用递推循环只保留前两个值// 文件路径com/example/recursion/FibonacciLoop.java public class FibonacciLoop { public static long fib(int n) { if (n 0) { throw new IllegalArgumentException(n 必须是正整数); } if (n 1 || n 2) { return 1; } long prev1 1; long prev2 1; long result 0; for (int i 3; i n; i) { result prev1 prev2; prev1 prev2; prev2 result; } return result; } public static void main(String[] args) { for (int i 1; i 40; i) { System.out.println(F( i ) fib(i)); } } }循环版本的时间复杂度是 O(n)空间复杂度是 O(1)既不会超时也不会栈溢出适合追求性能的生产场景。5.4 三种方案的复杂度对比实现方式时间复杂度空间复杂度主要风险朴素递归O(2^n)O(n)大量重复计算n 稍大就极慢记忆化递归O(n)O(n)缓存占用额外空间递推循环O(n)O(1)几乎无风险代码也简洁这段对比是整个递推递归学习里的一个分水岭。看懂之后你会明白递归不是不好而是要用对场合。当递归存在大量重叠子问题时必须做优化优化手段要么是记忆化要么是转成递推循环。这也正好解释了为什么动态规划题的很多解法看起来“和递推很像”动态规划本质上就是“带有状态定义的递推”只是在选择状态和转移方程时更复杂。6. 汉诺塔与递归回溯从斐波那契再看递归的通用性斐波那契的递归写法对应的是“一个递归调用依赖两个更小规模”属于二叉树形递归。汉诺塔问题展现了递归处理“多个子任务”时的优雅。汉诺塔规则有三根柱子 A、B、C。A 柱上有 n 个大小不同的圆盘按从小到大堆叠。要求把 n 个圆盘全部移动到 C 柱每次只能移动一个盘子且大盘子不能压在小盘子上。递归思路非常简洁先把上面 n-1 个盘子从 A 移到 B借助 C。把最大的第 n 个盘子从 A 移到 C。再把 B 上的 n-1 个盘子移到 C借助 A。这里的“n-1 个盘子移动”仍然是汉诺塔问题只不过柱子的角色发生了变化。Java 代码如下// 文件路径com/example/recursion/Hanoi.java public class Hanoi { /** * param n 盘子数量 * param from 起点柱 * param to 终点柱 * param aux 辅助柱 */ public static void hanoi(int n, char from, char to, char aux) { if (n 1) { System.out.println(Move disk 1 from from to to); return; } // 第一步把前 n-1 个盘子从 from 移到 aux hanoi(n - 1, from, aux, to); // 第二步移动最下面的第 n 个盘子 System.out.println(Move disk n from from to to); // 第三步把 aux 上的 n-1 个盘子移到 to hanoi(n - 1, aux, to, from); } public static void main(String[] args) { hanoi(3, A, C, B); } }程序输出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汉诺塔是理解递归执行顺序的最佳练习题之一。建议初学者不要直接看答案而是拿三张纸模拟一遍调用过程。你会发现代码只有短短十几行但执行顺序很容易绕晕。这背后藏着递归最有价值的地方我们只需要定义“当前层做什么”以及“更小规模的问题怎么调自己”不需要手动维护复杂的过程状态。代码用递归表达的复杂度和用循环表达的复杂度往往不在一个量级。类似的思想会继续延伸到很多“递归回溯”问题比如八皇后、全排列、数独求解。八皇后问题在程序里通常这样组织递归函数尝试在第 row 行放置皇后如果当前列能放就继续递归到下一行如果下一层递归失败就撤销当前放置尝试下一列。这种“先尝试失败回退”的过程在算法中被称为回溯本质是递归加上状态撤销。所以汉诺塔之后递归学习的下一个台阶就是“递归 回溯 剪枝”这也是 CSP 类问题求解的常见套路。7. 常见问题与排查思路把递归和递推写错是家常便饭。下面整理一份可以对照排查的表问题现象可能原因排查方式解决方案抛出 StackOverflowError递归没有出口递归参数没有向出口靠近n 太大打印进入函数时的参数补终止条件确认每层调用规模递减必要时改循环结果比预期少一项或多一项初值设错递归出口判断错误循环从 1 开始而不是从 3 开始用 n1、2、3 测试边界对齐数学递推式的初值n 到 40 左右程序越来越慢朴素递归存在大量重复子问题观察执行时间变化增加记忆化缓存或改成递推循环程序没有报错但一直运行递归进入死循环参数不再变化打印入口参数观察是否重复确认每次递归都修改了关键参数确保能到达出口负数转换结果异常Integer.MIN_VALUE 取负后溢出用边界值测试用 long 类型或单独处理最小负数递归结果正确但性能差函数调用频繁、栈帧开销大统计运行时间和内存对热点递归改写成递推循环实际排查时有一个非常高效的技巧先写一个只打印、不返回结果的观察函数看看每个递归层进入时的参数变化。例如private static void trace(int n) { System.out.println(进入递归当前 n n); if (n 1 || n 2) { return; } trace(n - 1); trace(n - 2); }如果打印出来的 n 没有持续减小而是出现重复值甚至增大递归结构就有问题。这个技巧可以应用到任何递归代码中比在脑子里硬推调用栈高效得多。8. 老书的工程建议递归怎么用最稳阅读老教材时你会发现它们不会提倡“所有递归都改成循环”因为递归的代码可读性和建模能力是循环难以替代的。更合理的建议是分场景选择。8.1 实际问题中先写递推式再写代码拿到递归题先别急着写代码。在纸上写出递推关系明确边界条件。写不出来递推式代码写出来也容易是“背模板”。比如爬楼梯、斐波那契、铺砖问题递推式几乎一样但题目表现不同。先写递推式会迫使你思考问题结构而不是死记题型。8.2 递归代码的“三件事”原则每次写递归函数前先回答三个问题并把答案写进注释这个函数解决什么问题。递归出口是什么。当前层如何通过子递归结果组合出最终结果。以遍历目录为例一个递归函数应该先写清楚返回当前目录及其所有子目录下的文件数递归的出口是“当前目录没有子目录”只统计当前目录下的文件后返回当前层把每个子目录的递归结果相加。如果递归函数超过一屏优先拆函数而不是把它写成一大坨。许多调试成本都来自“递归函数内部既做拆分又做统计又做清理”职责不明。8.3 能递推就不递归、要递归就加保护在工程里不能简单说递归比递推好也不能反过来。更务实的策略是问题天然是树形结构且递归代码清晰优先递归。递归深度可能很大或性能敏感优先循环。不得不使用递归时对输入规模做约束避免不可控的栈溢出。存在大量重叠子问题时考虑记忆化或直接转成动态规划。递归里不要修改全局状态除非你清楚知道自己在做回溯。另外很多团队对递归深度会加硬性上限。例如 Java 默认线程栈大小通常在 512KB 到 1MB 左右某些环境下递归深度在几千层就可能溢出。如果需要在生产环境处理深层嵌套结构要么转成显式栈要么在实现时保留一个深度计数器达到阈值后抛出业务异常。8.4 用测试和边界值加固递归代码递归最容易在边界处出错。建议至少覆盖以下用例最小输入比如 n1、n2。边界输入比如输入 0、负数。超大输入确认不会超时或溢出。输入中带符号的数字验证正负号拼接顺序。代码里多写断言把不合法输入在入口挡住。很多递归问题调试半天最后发现是调用方传入了负数或 0。9. 总结递推公式是地图递归是执行循环是油门回到最开始的困惑。递推和递归学不会通常不是“记不住定义”而是没有把一个数学关系从脑子里的公式翻译成程序里的执行路径。这本老书给我的最大启发是一条可复制的学习路径先观察数列写出递推式和初值。用循环递推实现一次感受“从前往后推”的过程。用递归实现一次画出它的调用树标出出口和回溯过程。用记忆化或递推循环处理性能问题比较不同写法的优劣。如果你愿意按这个方法做三道题每一道都用递推、递归、记忆化三种方式写一遍你对递推和递归的感觉会完全不一样。下一阶段可以继续深入分治算法、回溯算法和动态规划。你会发现这些看起来更高级的算法本质上仍然在回答同一个问题一个大的问题状态如何拆成更小的问题状态再把子结果组合起来。遇到题目时多问自己三句有没有递推式边界在哪里能不能用循环解决把这套思维练成习惯递推与递归就不再是“玄学”而是你分析问题的一个稳定工具。