1. 递推不是递归先把这个基本概念掰扯清楚很多初学者第一次接触递推时都会把它和递归搞混。我当年也是这样——直到被一道递推题虐了整整一个晚上才真正理解两者的本质区别。先说结论递推是一种从已知推未知的思维方式它从你已经确定的值出发一步步推导出后面的值。而递归是自己调用自己它从一个待求的问题出发不断拆分成更小的子问题直到拆到可以直接求解的规模然后再逐层返回结果。举个最直观的例子斐波那契数列。递推的写法是从前往后算function fibonacci(n) { if (n 1) return n; let prev 0, curr 1; for (let i 2; i n; i) { let next prev curr; prev curr; curr next; } return curr; }递归的写法是从后往前拆function fibonacciRecursive(n) { if (n 1) return n; return fibonacciRecursive(n - 1) fibonacciRecursive(n - 2); }两者用同一个递推式 f(n) f(n-1) f(n-2)但思考方向和执行路径完全不同。递推是自底向上递归是自顶向下。递归代码往往更接近数学定义、更容易写出来但效率可能很糟糕——上面这个朴素的递归实现时间复杂度是指数级的n40 就要算很久。而递推只需要一个循环时间复杂度 O(n)。我见过太多人在面试或者笔试里一上来就写递归然后被时间复杂度卡住。递推的价值恰恰在于当你已经掌握了问题的最优子结构用递推可以从容地按顺序把中间结果全部算出来不重复、不遗漏。还有一个很容易被忽略的点递推不只在编程里有它在数学、组合计数、概率论、运筹学里无处不在。数列的递推公式、动态规划的状态转移方程、矩阵快速幂的构造本质上都是递推思想的产物。所以学好递推是在给后面一整套算法知识打地基。2. 按顺序推导型递推从斐波那契到爬楼梯问题这类问题是递推里最基础、也最能说明问题的一类结果只依赖有限个前驱状态推导方向单一明确。理解了这一类递推的骨架就搭起来了。2.1 爬楼梯问题的完整推导过程爬楼梯问题一次可以走 1 级或 2 级台阶问走到第 n 级台阶有多少种走法。我第一次做这道题时第一反应是枚举——n3 是 3 种n4 是 5 种n5 是 8 种。数着数着发现规律了3, 5, 8这不就是斐波那契数列从第三项开始吗但发现规律和证明规律是两回事真正要理解的是这个递推式怎么来的。关键思路是这样要走到第 n 级台阶最后一步只有两种可能——从第 n-1 级走 1 级上来或者从第 n-2 级走 2 级上来。于是走到第 n 级的走法总数就等于走到第 n-1 级的走法数加上走到第 n-2 级的走法数f(n) f(n-1) f(n-2)这个推导过程的精髓在于**倒过来想**。不从第一步开始数有多少种分支而是盯着最后一步做分类。这种以末尾状态分类的思路是递推也是后面动态规划里最常用的手法。边界条件也要一起定好f(1) 1f(2) 2。注意这里不是 f(0) 0因为 2 级台阶可以一次走 2 级也可以走两次 1 级是 2 种走法。很多新手死就死在边界上——把边界当成斐波那契的 f(1)1, f(2)1 直接套结果全错。2.2 为什么递推比递归更适合这类问题还是拿爬楼梯说事。如果完全按递推式写递归def climb_stairs(n): if n 1: return 1 if n 2: return 2 return climb_stairs(n - 1) climb_stairs(n - 2)n30 就已经肉眼可见地卡顿了。原因是它把同一个子问题反复计算了无数遍——比如 climb_stairs(20) 在计算 climb_stairs(30) 的过程中会被调用多少次答案是几百次。这就是经典的重叠子问题。递推的方式则是开一个数组从下标 1 开始一个一个往后填def climb_stairs_dp(n): if n 1: return 1 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]每个状态只算一次后面的结果直接查前面的结果这就是递推的威力所在。需要注意的是很多教材会把这种动态规划写法称为记忆化搜索自底向上版。其实名字不重要重要的是你建立了当前状态依赖哪些前置状态的直觉。一旦这个直觉建立起来后面看到任何递推式的题目你脑子里都会自动浮现一条填表的主线。3. 分类讨论型递推错排问题和卡特兰数的思维门槛如果你以为递推就是前两项相加那遇到错排问题的时候就会懵。这类递推的核心不是顺序推导而是基于具体情况做分类讨论每一类都对应一个前置状态。这是递推里第一个真正的分水岭。3.1 错排问题的递推式是怎么想出来的错排问题有 n 封编号为 1 到 n 的信和 n 个编号相同的信封要求每封信都不能装进对应编号的信封里问有多少种装法记作 D(n)。D(1)0D(2)1这个好算。关键是 D(n) 的递推式我第一次看到这个推导时觉得非常精妙。思路是这样的先看第 1 封信它不能装进 1 号信封于是它有 n-1 种选择。假设它装进了第 k 号信封k ≠ 1现在来讨论第 k 封信的位置分两种情况第 k 封信恰好装进了 1 号信封。这样第 1 封和第 k 封就互相交换了位置剩下的 n-2 封信要满足错排条件一共 D(n-2) 种。第 k 封信没有装进 1 号信封。这里是最绕的地方我们可以把 1 号信封虚拟地看成第 k 封信的对应信封意思是要求第 k 封信不能进 1 号信封。这样问题就等价于 n-1 封信做了错排一共 D(n-1) 种。于是D(n) (n-1) × (D(n-1) D(n-2))这个递推式看起来简单但把 1 号信封视作第 k 封信的信封这一步需要很强的抽象替换能力。我当时是在纸上把 n4 的所有情况列了一遍才彻底想通。这类问题的共通套路是抓住一个特殊元素这里是第 1 封信讨论它的去向再看这个去向如何影响剩余元素的结构。一旦结构被厘清递推式就水到渠成。3.2 卡特兰数递推里的求和型结构卡特兰数是另一类经典递推递推式长这样C(n) C(0)×C(n-1) C(1)×C(n-2) ... C(n-1)×C(0)边界 C(0) 1。它对应的问题多到令人发指n 对括号的合法括号序列数量、n 个节点的不同形态二叉树数量、n 个元素进栈出栈的合法序列数量、凸 n 边形三角剖分方案数……全是同一个数列。以括号序列为例一个合法括号序列的最左端一定是左括号找到一个右括号和它匹配这个右括号把整个序列分成两部分——内部和剩余部分。内部是长度为 2k 的合法括号序列剩余部分是长度为 2(n-1-k) 的合法括号序列于是C(n) Σ C(k) × C(n-1-k)其中 k 从 0 到 n-1看明白了吗递推式不是凭空想出来的它是对原问题做了一次结构性分解——找到第一个匹配的右括号把问题切片成两个独立的子问题。这种分解思想比记住卡特兰数本身更重要因为你在排列组合、树形动态规划的题目里都会反复用到。3.3 错排和卡特兰的代码实现差异错排是加法型递推一重循环搞定卡特兰是求和型递推需要二重循环。代码不难但复杂度有区别def derangement(n): if n 1: return 0 if n 2: return 1 d [0] * (n 1) d[1] 0 d[2] 1 for i in range(3, n 1): d[i] (i - 1) * (d[i - 1] d[i - 2]) return d[n]def catalan(n): c [0] * (n 1) c[0] 1 for i in range(1, n 1): for j in range(i): c[i] c[j] * c[i - 1 - j] return c[n]卡特兰的二重循环是 O(n²)好在它的应用场景里 n 通常不会太大。如果 n 很大就得用它的通项公式 C(n) C(2n, n) / (n1) 配合大数运算来算这是后话。4. 网格路径递推二维状态表的建立与滚动数组优化二维递推是另一个大坑。前面讲的都是一维的数列一个方向推到头。但现实中很多问题的状态有两个维度比如坐标、物品数量、剩余容量。网格路径问题就是最典型的二维递推入门题。4.1 从 (1,1) 到 (m,n) 的路径计数问题在一个 m 行 n 列的网格中从左上角走到右下角每次只能向下或向右走问有多少条不同的路径?这个问题的递推式非常直观dp[i][j] dp[i-1][j] dp[i][j-1]含义是到达 (i, j) 这个格子只能从上方 (i-1, j) 走下来或者从左方 (i, j-1) 走右过来。所以到达当前格子的路径数等于两个来源之和。边界条件是第一行的格子只能从左往右走所以 dp[1][j] 1第一列的格子只能从上往下走所以 dp[i][1] 1。填表过程也很好理解从第二行第二列开始逐行逐列地填每个格子都依赖它的上方和左方这两个值在填表时都已经算好了。def unique_paths(m, n): dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): dp[i][1] 1 for j in range(1, n 1): dp[1][j] 1 for i in range(2, m 1): for j in range(2, n 1): dp[i][j] dp[i - 1][j] dp[i][j - 1] return dp[m][n]这个递推的每一步都是在回答一个从哪来的问题。如果你把视角从每个格子换成每个状态你会发现它和爬楼梯没有本质区别——都是当前状态 所有能到达当前状态的前置状态之和。4.2 为什么要有二维数组状态之间的依赖方向理解二维递推的一个关键是搞清楚状态之间的依赖方向。在网格路径问题里依赖方向是从左上方到右下方——dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]这两个状态的信息传播方向永远指向右下方。这保证了按行从左到右、从上到下填表时依赖值永远先于当前值被算出来。反过来如果某个递推式的依赖方向是双向的、回环的那就不能用简单的填表法求解得另想办法。这是递推和动态规划里无后效性概念的直观体现——后面的状态只依赖前面的状态不受未来影响。4.3 滚动数组优化把 O(mn) 的空间压到 O(n)很多教材会直接告诉你用滚动数组优化空间但不解释为什么能这样优化。其实原因在上面已经提到了dp[i][j] 只依赖上一行i-1 行和当前行i 行的左边一个格子。也就是说当你算第 i 行的时候第 i-2 行及之前的所有数据已经完全没用了。所以不需要保存整个二维表只需保留两行更极限的是只保留一行def unique_paths_optimized(m, n): dp [1] * n # 初始化第一行全部只有从左往右一种走法 for i in range(1, m): for j in range(1, n): dp[j] dp[j - 1] return dp[-1]这个一维数组的精妙之处在于dp[j] 在更新前存的是上一行的值相当于 dp[i-1][j]而 dp[j-1] 在更新后已经是当前行的值相当于 dp[i][j-1]。两者相加正好得到 dp[i][j]。我在第一次看懂这个写法时确实有被惊艳到——递推问题的空间优化往往就是在哪些数据还需要这个问题上做文章。网格路径问题的思路可以无缝迁移到很多场景有障碍物的路径计数遇到障碍物就把 dp 值设为 0、带权值的最小路径和dp[i][j] 改成取 min、以及后续动态规划里的背包问题同样用滚动数组优化空间。这类递推的模型一旦吃透会让你的状态设计能力上一个台阶。5. 递推式求解的进阶手段特征方程与矩阵快速幂递推式本身是怎么算的描述但当你面对一个递推式时往往还关心另一个问题能否不一项一项算直接求出第 n 项这就是递推式的通项公式求解。这里我只说两个高频手段它们在实际竞赛和工程问题中非常实用。5.1 线性递推与特征方程对于形如 f(n) a×f(n-1) b×f(n-2) 的线性常系数齐次递推可以通过特征方程求通项。以斐波那契为例f(n) f(n-1) f(n-2)特征方程是 x² x 1解得 x₁ (1√5)/2x₂ (1-√5)/2。于是通项为f(n) A×x₁ⁿ B×x₂ⁿ把 f(0)0f(1)1 代入解出 A 和 B就得到比内公式。坦白说通项公式在这个时代用得不算多——因为求特征方程、解系数这套流程在计算机上反而不如直接 O(n) 递推高效。它更大的价值在于理论分析通过特征根可以判断递推数列的增长速度、周期性、收敛性等性质这在分析算法复杂度时有用。5.2 矩阵快速幂把 O(n) 变成 O(log n)真正在实战中高频使用的是矩阵快速幂。还是以斐波那契为例递推关系可以写成矩阵形式[ f(n) ] [ 1 1 ] × [ f(n-1) ] [ f(n-1) ] [ 1 0 ] [ f(n-2) ]也就是说[ f(n) ] [ 1 1 ]^(n-1) × [ f(1) ] [ f(n-1) ] [ 1 0 ] [ f(0) ]利用矩阵乘法的结合律可以用快速幂在 O(log n) 时间内求出矩阵的 n-1 次幂从而得到 f(n)。def mat_mul(a, b): return [ [a[0][0]*b[0][0] a[0][1]*b[1][0], a[0][0]*b[0][1] a[0][1]*b[1][1]], [a[1][0]*b[0][0] a[1][1]*b[1][0], a[1][0]*b[0][1] a[1][1]*b[1][1]] ] def mat_pow(mat, n): res [[1, 0], [0, 1]] # 单位矩阵 while n: if n 1: res mat_mul(res, mat) mat mat_mul(mat, mat) n 1 return res def fib_matrix(n): if n 0: return 0 base [[1, 1], [1, 0]] result mat_pow(base, n - 1) return result[0][0]我建议你亲手推一遍这个矩阵乘法的过程因为很多递推题目的状态不止一个数而是一组数比如 f(n)、g(n) 互相依赖这时候构造转移矩阵的能力就变得至关重要。只要你能把一个递推系统写成状态向量 转移矩阵 × 上一状态向量的形式就都能用矩阵快速幂加速。矩阵快速幂的适用条件是递推是线性的、系数是常数、阶数不高。如果递推带上了和 n 相关的系数或者状态之间是非线性关系这条路就走不通了。6. 递推实战中的隐形陷阱边界、溢出与取模递推的代码通常不长但恰恰是这种看起来简单的题目最容易在细节上翻车。我在这里整理了四个高频坑每一个都是我或我身边的朋友在实战中踩过的。6.1 边界条件的设计失误边界是递推题出错的重灾区。常见的问题包括把 f(0) 和 f(1) 的初始值设反。比如爬楼梯问题f(1)1、f(2)2而不是 f(0)0、f(1)1。虽然算到后面数值一样但中间逻辑会出问题。忽略 n 取极小值的情况。n0 或 n1 时递推循环根本不进去函数必须在一开始就正确返回。如果没处理数组会越界。递推公式的适用范围没搞清楚。比如错排问题 D(1)0、D(2)1这两个特殊值必须单独定义因为递推式 D(n)(n-1)(D(n-1)D(n-2)) 在 n2 时依赖 D(0)而 D(0) 往往没有定义。我的习惯是写完递推函数后先手动代入 n1、2、3 跑一遍确认初始值和前几项都符合直觉。6.2 整数溢出斐波那契增长比你想象中快斐波那契数列第 46 项大约是 18 亿刚好是 int32 能表示的上限附近。第 93 项就超过了 int64 的上限。如果你用的语言默认整数是 32 位的算到 n50 就会溢出结果变成负数或者被截断。增长更夸张的递推还有很多比如卡特兰数的增长速度接近 4ⁿ/n^(3/2)。所以写递推代码时一定要先预估结果的数量级再决定用什么类型存储结果——Python 的大整数不用担心溢出但 C/Java 必须小心必要时使用 long long、BigInteger 或随时取模。6.3 取模操作的正确姿势竞赛和算法题里结果常常要求对 10⁹7 取模。递推式的取模遵循一个规则(f(n-1) f(n-2)) mod m ((f(n-1) mod m) (f(n-2) mod m)) mod m所以每一步都对中间结果取模是可以的、也是推荐的。但要注意不要只在最后取模。斐波那契不取模算到 n100 就已经是大数运算了中间值早就溢出。减法取模要小心负数在 C 里如果算 (d[i-1] - d[i-2]) % m结果可能是负数要加上 m 再取模。乘法取模时两个 int64 相乘可能溢出 64 位这时要用更宽的类型或者在支持大整数的语言里做。我的建议是凡是涉及递推的算法题默认每一步取模除非题目明确说不需要。6.4 调试递推代码的土办法递推代码逻辑错了最好的调试方式不是断点而是打印前几项。把数组的前 10 项打出来和手算/已知结果对照。递推的每项都依赖前项所以只要前几项对上了后面基本不会出错如果第 5 项开始偏离说明递推式里有隐藏 bug重点检查状态转移方程和边界条件。7. 从递推到动态规划状态转移方程的思维跃迁到了这一节我想聊一个更宏观的问题递推和动态规划到底什么关系很多人觉得动态规划难其实动态规划的核心就是一个递推式状态转移方程 一个填表顺序。你在前面学的递推能力几乎可以无缝迁移到动态规划里。区别在于动态规划的状态设计更自由、更抽象——递推里的状态是第 n 项动态规划里的状态是在某个限制条件下的最优值/方案数但它依然是当前状态依赖前面若干已经算好的状态。以经典的一维动态规划——打家劫舍为例一排房子不能偷相邻的两家问能偷到的最大金额。状态设计为 dp[i] 表示偷到第 i 家时的最大金额状态转移为dp[i] max(dp[i-1], dp[i-2] nums[i])这不就是递推吗只是把求和换成了取最大值。你在爬楼梯里积累的填表思路在这里一模一样地适用。再比如背包问题dp[i][j] 表示前 i 个物品装入容量为 j 的背包的最大价值转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])二维、依赖左上方状态、按行填表——这跟网格路径递推是同构的问题结构。所以我的建议是不要等学到动态规划时再临时抱佛脚。在学递推的阶段就主动把每一道题都当成状态设计练习来做——问自己三个问题这个问题的状态是什么用哪个变量或哪几个变量能唯一描述一个子问题当前状态依赖哪些前置状态它们之间是什么运算关系加、乘、取 max、取 min填表的顺序是什么边界值是什么把这三个问题想清楚递推式自然就写出来了。这个思维模式会伴随你走完整条算法学习之路。最后说一点个人体会递推的魅力在于它让复杂的计数问题变得机械而确定。一旦递推式建立剩下的只是按部就班地填表。难的不是实现而是推导——而推导的本质是对问题结构的理解。多花时间在这个递推式为什么长这样上远比多刷几道模板题更有价值。