递推与递归的区别：从斐波那契数列到动态规划

数列、递推、递归这三个词在计算机课程里经常连在一起出现也会在期末、竞赛和面试里被反复考查。不少读者反馈递推公式看得懂用循环也能写出结果但一遇到递归函数执行顺序就乱不知道什么时候该 return什么时候该继续调用更说不清递归和递推到底有什么本质区别。数学里明明是“由前两项推后一项”的平铺直叙放到程序里却像在不断“套娃”很容易绕晕。这篇文章会把“数列 → 递推 → 递归”这条逻辑链完整梳理一遍用斐波那契数列作为主线从数学递推式开始讲到数组递推、滚动变量、递归函数、记忆化搜索再到经典的“整数转字符串”“汉诺塔”等题目。哪怕你以前听递推和递归就头疼跟着本文把每条代码亲手敲一遍也能建立起清晰的概念框架。1. 递推、递归与数列先建立整体认知1.1 从“第三项等于前两项之和”说起“数列第一项是 1第二项也是 1从第三项开始每一项等于前两项之和。”这是一道很常见的数列填空题它描述的其实就是一个典型的递推式。写成数学语言就是F(1) 1 F(2) 1 F(n) F(n-1) F(n-2)其中 n ≥ 3这就是斐波那契数列的递推定义。理解这个式子之后你会发现“递推式”这个词也没有那么神秘它只是在说明当前项必须依赖前面若干项才能算出来。很多初学者的问题在于以为学数列就是学“通项公式”于是总想找到一个公式直接算出第 n 项。但计算机算法里更重要的是“递推关系”只要给定足够多的初始状态就能沿着顺序一项一项往后推最终推出我们需要的第 n 项。通项公式可以算得很快但递推方法才是编写程序、解决动态规划问题的基础思维。1.2 递推是“从前往后算”递归是“从后往前拆”“递推”和“递归”在中文里只差一个字学习时非常容易混。我们先看它们的定义差别递推从已知边界出发一步步推出后面的结果。比如已知 a1、a2用循环算出 a3、a4、a5……一直到 an。这是一个“自底向上”的过程。递归把一个大问题不断拆成同类的小问题直到小问题可以直接回答再逐层把答案带回去。比如想求 F(10)就先去求 F(9) 和 F(8)而求 F(9) 又要求 F(8) 和 F(7)。这是一个“自顶向下”的过程。举个例子。如果要求斐波那契数列的第 10 项递推思路先算 F(1)1F(2)1得到 F(3)2再得到 F(4)3……一步一步推到 F(10)。递归思路把 F(10) 拆成 F(9)F(8)再把 F(9) 拆成 F(8)F(7)一路拆到 F(1)、F(2) 这两个不需要再拆的边界条件然后把结果逐层返回。从程序实现来看递推通常对应循环结构递归通常对应函数调用自身。但两者描述的是同一个数学问题所以它们之间可以互相转化。1.3 为什么总要放在一起学数列题里常见的是递推式算法题里常见的是递归函数而在数据结构中树的遍历、图的搜索又都依赖递归思想。把这几个概念放在一起是因为它们共享同一个底层逻辑将一个大问题的求解转换为若干个小问题的求解。如果未来你接触动态规划会发现“状态转移方程”本质上就是一个递推式。如果你学习回溯算法会发现它是在递归结构上增加“撤销选择”的操作。递归和递推像是一枚硬币的两面一面偏数学表达一面偏程序执行。2. 递推公式与数列怎么把数学式变成程序2.1 递推公式的几种常见形态递推公式不止斐波那契一种。在数列和算法题目里常见的递推形态有类型递推关系典型说明等差数列an a(n-1) d公差固定等比数列an a(n-1) * q公比固定斐波那契型an a(n-1) a(n-2)前两项之和阶乘型an n * a(n-1)乘上前一项汉诺塔型an 2 * a(n-1) 1每次多一步整体搬移这些递推式在程序里写起来并不难关键是要先确定两件事边界条件哪些项不需要推是已知的递推起点从第几项开始才能安全地访问前面的项比如斐波那契数列需要用到 F(n-1) 和 F(n-2)意味着循环必须从 n3 开始否则下标会越界。这是初学者最容易忽略的细节。2.2 最小示例用数组递推斐波那契数列来看一段可以在本地直接编译运行的 C 语言代码。它的思路很简单开一个数组把 F(1) 和 F(2) 初始化然后从第 3 项开始循环向后填。// 文件路径fib_array.c #include stdio.h int main(void) { int n 20; long long f[25] {0}; f[1] 1; f[2] 1; for (int i 3; i n; i) { f[i] f[i - 1] f[i - 2]; } for (int i 1; i n; i) { printf(F(%d) %lld\n, i, f[i]); } return 0; }代码说明如下数组下标从 1 开始使用所以数组大小至少要比 n 大 1。使用long long而不是int是因为斐波那契数列增长非常快第 47 项之后就会超过int的表示范围。循环从i 3开始保证f[i - 1]和f[i - 2]已经初始化。这段程序运行后会依次打印F(1) 1 F(2) 1 F(3) 2 F(4) 3 F(5) 5 F(6) 8 ... F(20) 6765如果你的输出能看到这些数字说明你已经完成了“数学递推式 → 数组循环程序”的第一步转换。2.3 用滚动变量把空间优化到 O(1)仔细观察上面的代码会发现数组里主要用到的其实只有前两个值f[i-1]和f[i-2]。如果我们只需要第 n 项并不想把前 n-1 项全部存下来可以用两个变量滚动更新。// 文件路径fib_rolling.c #include stdio.h int main(void) { int n 20; long long a 1; // F(1) long long b 1; // F(2) if (n 1) { printf(F(1) %lld\n, a); return 0; } if (n 2) { printf(F(2) %lld\n, b); return 0; } for (int i 3; i n; i) { long long c a b; a b; b c; } printf(F(%d) %lld\n, n, b); return 0; }这里的关键是每次循环之后把b赋值给a把新算出的c赋值给b。这样原来的F(n-1)就变成了下一次计算里的F(n-2)原来的F(n)就变成了下一次计算里的F(n-1)。滚动变量在很多算法题中是常用的优化手段它的空间复杂度只有 O(1)。不过缺点是如果后面还需要输出整条数列仍然要使用数组保存中间结果所以并不存在“数组一定差、滚动一定好”的说法需要根据题目需求选择。2.4 什么时候优先考虑递推递推方法适合以下场景问题存在明确的状态转移关系并且依赖方向是单向的。求解顺序可以按自然数递增排列不需要频繁跳跃。递归深度可能非常大的情况循环通常更安全、更高效。动态规划里的“填表法”就是递推思想的直接体现。比如背包问题、最长上升子序列、数塔问题第一步都是先找到状态定义和状态转移方程再用二重循环填表。3. 递归从“自己调用自己”到“调用栈思维”3.1 递归函数的三要素很多教材在讲解递归时会写“函数调用自己”。这个说法虽然没错但初学者会更困惑如果函数一直调用自己不会没完没了地循环吗所以要真正理解递归需要看递归的三要素边界条件递归到什么时候必须停止这个条件也叫递归出口。递归调用函数内部要调用自己但调用时问题的规模必须变小。子问题与原问题同构子问题应该和原问题属于同一类问题只是规模更小。先看一个最简单的例子求 n 的阶乘。// 文件路径factorial.c #include stdio.h long long factorial(int n) { if (n 0 || n 1) { return 1; } return n * factorial(n - 1); } int main(void) { for (int i 1; i 10; i) { printf(%d! %lld\n, i, factorial(i)); } return 0; }在这个函数中n 0 || n 1是边界条件此时直接返回 1。return n * factorial(n - 1);是递归调用每次调用 n 都减少 1。求 n! 的问题被拆成了 n 乘以求 (n-1)! 的问题两者是同类问题。运行后输出的结果和数学上的阶乘定义完全一致。如果你把边界条件去掉那么函数会一直调用自己造成无限递归最终程序崩溃。3.2 进入递归和退出递归的顺序递归难以理解其实不在于“调用自己”而在于“执行顺序”。我们可以在函数入口和出口各加一句打印直观观察递归的执行轨迹。// 文件路径trace.c #include stdio.h void func(int n) { printf(enter n %d\n, n); if (n 1) { printf(base n 1, return\n); return; } func(n - 1); printf(leave n %d\n, n); } int main(void) { func(3); return 0; }运行结果如下enter n 3 enter n 2 enter n 1 base n 1, return leave n 2 leave n 3从输出里可以看到程序并不是在输出完enter n 3之后立刻执行leave n 3而是要等func(2)全部执行完再回到 n3 这层。这个“先一路向下再一级一级返回”的过程背后是计算机的函数调用栈。每次调用函数系统都会在栈上分配一块栈帧记录参数、局部变量和返回地址。递归调用时栈帧不断叠加当遇到边界条件开始 return 时栈帧再逐层释放。理解了这一点你就知道为什么下面这段代码输出结果会是反的void printBackward(int n) { if (n 0) return; printf(%d , n); // 先输出 printBackward(n - 1); }调用printBackward(3)会输出3 2 1而不会是1 2 3。递归调用前后代码的执行时机是新手最容易踩的坑。3.3 经典题目递归法将一个整数 n 转换成字符串在 C 语言学习中有一道非常经典的递归题输入一个整数 n不使用printf(%s)之类的现成格式化方式用递归将整数转换成字符串并输出。比如输入1234希望输出1234。最容易想到的思路是把整数不断除以 10直到剩下的最高位然后从最高位开始逐位输出。如果正向写循环需要先把每一位存到数组里再倒序遍历。而用递归可以很自然地实现“先处理高位再输出低位”。// 文件路径int2str.c #include stdio.h void numberToString(int n) { if (n 0) { putchar(-); // 注意这里用 n -n 会有 INT_MIN 溢出的风险 // 本示例只演示核心逻辑实际开发建议改用 long long 类型保存 n -n; } if (n 10) { numberToString(n / 10); } putchar(0 n % 10); } int main(void) { numberToString(1234); putchar(\n); numberToString(0); putchar(\n); return 0; }关键点在于这一句numberToString(n / 10); putchar(0 n % 10);递归调用发生在putchar之前所以程序会一直递归到最高位先输出最高位的字符再在返回过程中依次输出后面的数字。以1234为例numberToString(1234)判断 1234 10调用numberToString(123)。numberToString(123)判断 123 10调用numberToString(12)。numberToString(12)判断 12 10调用numberToString(1)。numberToString(1)不满足 n 10直接输出字符1。返回到 n12 这一层输出2。返回到 n123 这一层输出3。返回到 n1234 这一层输出4。最终看到的就是1234。这个例子很重要因为它演示了“递归的输出顺序”如何与“递归处理顺序”相反地组合起来。很多字符串反转、逆序输出、树的遍历题目都基于这种顺序控制技巧。3.4 递归的执行代价函数调用栈不是无限的递归虽然表达自然但它需要消耗函数调用栈空间。每递归一层都会创建新的栈帧。如果递归层数很深就可能把调用栈耗尽导致程序崩溃典型报错有Linux 环境下Segmentation faultWindows 环境下Stack overflowJava 中StackOverflowError栈空间大小由操作系统和编译器决定常见默认值在几 MB 左右。如果每层递归使用的局部变量比较多栈帧会更大几千层递归就可能发生溢出。正因如此递归在实际工程中要特别注意深度。对于极端输入比如 n 高达 100000 的递推问题优先选择循环实现如果必须使用递归也可以尝试改成“尾递归”或者显式使用栈模拟。尾递归指的是递归调用是函数体内最后一个操作返回值不需要再做额外运算。例如求阶乘的“尾递归版本”long long factorialTail(int n, long long acc) { if (n 0 || n 1) { return acc; } return factorialTail(n - 1, acc * n); }这里每次递归时把当前的累积结果传给下一层返回时直接返回递归调用的结果不再做乘法。部分编译器支持尾递归优化会把这种递归自动改写成循环从而避免栈溢出。但要注意C 语言并不强制要求编译器做尾递归优化不同编译器的处理方式不同。因此工程中不能盲目依赖尾递归优化更稳妥的做法是直接用循环。4. 同一个斐波那契四种写法系统对比为什么要反复用斐波那契数列做例子因为它非常适合对比不同写法的性能差异而且你能直观看到“递推”和“递归”在解决同一个问题时程序结构、时间复杂度和空间复杂度到底差在哪里。下面假设我们要解决这样一个问题给定 n求斐波那契数列第 n 项其中 n 的范围可能达到较大规模。4.1 纯递归表达最自然但性能最差先写一个最直观的递归版本// 文件路径fib_rec.c #include stdio.h long long fibRec(int n) { if (n 1 || n 2) { return 1; } return fibRec(n - 1) fibRec(n - 2); } int main(void) { int n 20; printf(F(%d) %lld\n, n, fibRec(n)); return 0; }这个版本的代码和递推式几乎一一对应看上去非常简单。但问题是它的运行时间会指数级爆炸。原因是求fibRec(10)需要算fibRec(9)和fibRec(8)而求fibRec(9)又会去算fibRec(8)和fibRec(7)。同一个fibRec(8)在其中被重复计算了多次。如果把每次函数调用画成二叉树会发现树的节点数接近 2 的幂次也就是说时间复杂度大约是 O(2^n)。当 n30 时递归调用次数已经到百万级当 n40 时调用次数会增长到上亿级别。对于普通个人电脑程序会明显卡顿甚至长时间无法结束。这就是纯递归最典型的性能问题大量重复计算。4.2 加一个“小笔记本”记忆化递归既然性能问题出自重复计算那解决方案也很直接把已经算过的结果保存起来下次直接查表返回。// 文件路径fib_memo.c #include stdio.h long long memo[50] {0}; long long fibMemo(int n) { if (n 1 || n 2) { return 1; } if (memo[n] ! 0) { return memo[n]; } memo[n] fibMemo(n - 1) fibMemo(n - 2); return memo[n]; } int main(void) { int n 45; printf(F(%d) %lld\n, n, fibMemo(n)); return 0; }在递归计算之前先检查memo[n]是否已经非 0。如果非 0说明之前已经算过这个值直接返回。每个 n 最多只计算一次时间复杂度从指数级降到了 O(n)。这种“递归 缓存中间结果”的写法叫记忆化搜索。它保留了递归的直观结构又避免了重复计算是学习动态规划时非常重要的过渡方法。4.3 数组递推自底向上填表递归加记忆化仍然需要层层调用函数虽然时间复杂度是 O(n)但函数调用本身还有额外开销。如果你习惯“递推”思维可以直接用数组从底向上填表// 文件路径fib_dp_table.c #include stdio.h long long fibTable(int n) { if (n 1 || n 2) { return 1; } long long f[100] {0}; f[1] 1; f[2] 1; for (int i 3; i n; i) { f[i] f[i - 1] f[i - 2]; } return f[n]; } int main(void) { int n 45; printf(F(%d) %lld\n, n, fibTable(n)); return 0; }这段代码的优点是从小到大计算不涉及函数调用栈运行效率很高。但空间是 O(n)需要保存整张表。如果题目不仅要求输出第 n 项还要求输出前 n 项这种数组递推写法最合适。4.4 滚动递推时间和空间都友好如果只需要最终的第 n 项不要求保留前 n-1 项那么可以使用上一节讲过的滚动变量将空间复杂度优化到 O(1)。long long fibRolling(int n) { if (n 1 || n 2) { return 1; } long long a 1; long long b 1; for (int i 3; i n; i) { long long c a b; a b; b c; } return b; }四种写法对比如下表实现方式时间复杂度空间复杂度优点缺点纯递归O(2^n)O(n) 栈深代码最直观贴近数学定义大量重复计算性能差记忆化递归O(n)O(n)保留递归结构适合复杂状态转移函数调用开销较大数组递推O(n)O(n)编码简单可保留每一项空间浪费滚动递推O(n)O(1)性能最佳空间最省只能保存最近几项实际开发中如果 n 不大用哪种都能运行但如果 n 很大或者题目有时间限制纯递归很可能会超时。最容易兼顾“好写”和“高效”的通常是数组递推或滚动递推。5. 由浅入深的三类实战题目理解概念后关键是做几道经典题。下面按难度递进给出三道有代表性的题目每题都会说明思路、核心代码和需要注意的坑。5.1 题目一输出斐波那契数列的前 n 项题目要求输入 n输出第 1 项到第 n 项斐波那契数。这道题直接考察递推式适合用来验证基础。// 文件路径print_fib.c #include stdio.h void printFibonacci(int n) { long long a 1, b 1; if (n 1) printf(%lld , a); if (n 2) printf(%lld , b); for (int i 3; i n; i) { long long c a b; printf(%lld , c); a b; b c; } printf(\n); } int main(void) { printFibonacci(10); return 0; }输出为1 1 2 3 5 8 13 21 34 55这道题最大的坑是long long的表示范围。斐波那契数列增长非常快F(47)2971215073 已经超出 32 位有符号整数范围。如果 n 较大建议在题目允许范围内使用long long如果 n 非常大需要高精度计算或模运算。5.2 题目二递归法将整数 n 转换成字符串并输出这道题在前面已经给出过完整代码这里把它当成一道独立题目再整理一遍思路分析整数转为字符串本质上是对每一位数字转成对应字符。如果直接使用循环从头取最高位需要先算出位数比较麻烦。递归方法先处理n / 10再输出当前位的n % 10可以天然按从高到低的顺序输出。边界情况n 0 时输出字符0。n 0 时先输出负号。如果 n 恰好是 32 位整型的最小值时直接取相反数会溢出建议用更大的类型保存或单独处理。题目变式也很常见要求把数字转成字符串并保存到字符数组中而不是直接输出。此时可以借助全局字符数组和一个下标变量。// 文件路径int2str_array.c #include stdio.h char result[64]; int pos 0; void intToStr(int n) { if (n 0) { result[pos] -; n -n; } if (n 10) { intToStr(n / 10); } result[pos] 0 n % 10; } int main(void) { intToStr(2025); result[pos] \0; printf(%s\n, result); return 0; }这道题之所以常被拿来考试是因为它同时考察了递归顺序、字符转换和边界处理属于综合题。5.3 题目三汉诺塔——递推算次数递归打印移动步骤汉诺塔是递归教学里的经典案例。假设有三根柱子 A、B、CA 柱上有 n 个大小不一的圆盘目标是全部移动到 C 柱每次只能移动一个圆盘且大盘不能压在小盘上。求解思路是先把上面 n-1 个圆盘从 A 移动到 B。再把最大的圆盘从 A 移动到 C。最后把 B 上的 n-1 个圆盘移动到 C。移动次数满足递推式H(1) 1 H(n) 2 * H(n-1) 1这个递推式可以推出通项H(n) 2^n - 1。如果你想求移动次数用循环递推即可long long hanoiCount(int n) { long long steps 0; for (int i 1; i n; i) { steps steps * 2 1; } return steps; }但题目如果要求打印出每一步移动过程就需要用递归// 文件路径hanoi.c #include stdio.h void hanoi(int n, char from, char to, char aux) { if (n 1) { printf(Move disk 1 from %c to %c\n, from, to); return; } hanoi(n - 1, from, aux, to); printf(Move disk %d from %c to %c\n, n, from, to); hanoi(n - 1, aux, to, from); } int main(void) { hanoi(3, A, C, B); return 0; }运行结果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这段代码最难理解的是参数顺序from表示当前起点柱to表示目标柱aux表示辅助柱。在每一个递归步骤中辅助柱和目标柱会不断交换位置所以写递归时一定要盯清楚参数位置不能只背代码。5.4 从“数列递归”到更广泛的“递归场景”在计算机世界里“递归”这个词不仅出现在算法函数中还常常出现在系统和工具的描述中。例如文件系统遍历递归地读取某个目录再读取该目录下的所有子目录。配置管理SVN 的忽略规则中可以配置是否递归地应用忽略目录规则。这里“递归”的意思是规则会应用到当前目录及其所有子目录。软件安装递归安装依赖包也就是先安装当前包依赖的其他包。在这些场景里“递归”描述的是“对整体以及整体内部的每一层反复执行相同操作”。它和编程中的递归思想一致但不一定以函数调用自身的形式出现。理解这个概念能帮你把“算法里的递归”和“日常工具里的递归”统一起来。遇到 SVN 忽略目录、命令行-r参数这类问题时也能更快理解“递归”带来的影响范围。6. 常见报错现象与排查思路递归和递推虽然代码量不大但出错率很高。下面整理几类高频问题遇到报错时可以直接对照排查。问题现象常见原因解决思路程序崩溃提示栈溢出递归没有终止条件或深度过大检查递归出口是否完备将深递归改成循环或栈模拟程序一直没有输出或卡死无限递归参数没有向边界靠近打印每一步的入参确认参数变化方向运行结果正确但特别慢存在大量重复子问题增加记忆化数组或改用递推循环输出顺序反了把输出语句写在了递归调用的前面想清楚是“递归前输出”还是“递归返回后输出”数组下标越界访问i-1、i-2时循环起点过小从最小安全下标开始循环并检查数组大小数字结果变成负数整数溢出改用long long或更高级的大数处理方式6.1 栈溢出怎么排查如果程序运行后直接崩溃并且报错信息里出现stack overflow、Segmentation fault先不要急着怀疑编译器问题。优先检查递归函数是否满足以下条件是否设置了边界条件。边界条件是否有可能到达。每次递归调用参数是否在向边界靠近。例如void badRecursion(int n) { printf(%d\n, n); badRecursion(n 1); // 参数越来越大永远不会停止 }这个函数完全没有终止条件会一直调用直到栈空间耗尽。如果只是忘记写某个if代码里还有别的函数先执行完可能错误并不会立刻暴露而是在数据量变大时才触发。所以排查栈溢出时建议先用小规模输入测试判断问题是否由递归深度引起。6.2 结果不对输出顺序反了“输出顺序反了”是递归初学者最典型的困惑。看这段代码void countDown(int n) { if (n 0) return; printf(%d , n); countDown(n - 1); }调用countDown(5)输出5 4 3 2 1如果把输出放在递归调用之后void countUp(int n) { if (n 0) return; countUp(n - 1); printf(%d , n); }调用countUp(5)输出1 2 3 4 5这说明递归调用前后的代码执行顺序非常关键。想要输出“从 1 到 n”可以先把递归调用写在前面让函数一路递归到最底层再在返回途中输出想要输出“从 n 到 1”则可以在递归调用前先输出。遇到顺序错误时先检查打印语句放在递归调用的哪一侧。6.3 性能太差如何判断是不是重复计算如果程序在 n 很小时正常n 变大后明显卡顿大概率是递归里存在大量重复子问题。最简单的验证方法是加入一个计数器// 文件路径fib_count.c #include stdio.h long long callCount 0; long long fibRec(int n) { callCount; if (n 1 || n 2) { return 1; } return fibRec(n - 1) fibRec(n - 2); } int main(void) { int n 30; printf(F(%d) %lld\n, n, fibRec(n)); printf(callCount %lld\n, callCount); return 0; }当 n30 时计数器会达到数百万级别。这时改成记忆化递归或递推循环运行时间会显著缩短。这类性能问题不是靠优化编译器能解决的必须调整算法结构。7. 最佳实践与学习路线建议7.1 写递归之前先写出数学递推式很多同学直接上来敲代码结果写着写着把自己绕晕。更稳妥的做法是先在纸上写出递推关系和边界条件。以“求第 n 个斐波那契数”为例纸面上的推导应该长这样边界条件 F(1) 1 F(2) 1 递推关系 F(n) F(n-1) F(n-2) n ≥ 3然后把F(n) F(n-1) F(n-2)直接翻译成代码。翻译时注意边界条件对应递归中的if出口。递推关系对应return中的递归调用。如果使用循环递推循环起点要比最大依赖项大 1。这道“翻译工序”能大幅减少边界错误。遇到复杂动态规划题时先列出状态转移方程再写代码也是同样的习惯。7.2 工程中优先使用“递归思想”谨慎使用“递归调用”递归的思维方式非常适合拆分复杂问题但函数递归调用并不是永远的最佳实现。工程代码里需要考虑调用栈深度、异常处理、可读性和可测试性。我建议遵循以下原则如果问题可以很方便地用循环解决优先用循环。如果递归深度可能超过几千层需要考虑改写成迭代或加显式栈。如果递归深度受题目限制且每个子问题会被重复计算优先考虑记忆化搜索或动态规划。使用递归处理树、链表、图这类天然具备递归结构的数据时递归仍然是非常合理的选择。实际项目里比如解析 JSON、遍历目录树、处理嵌套括号递归往往比手工维护栈更清晰。这时只要控制好输入规模、增加访问深度限制和日志就能把风险降到可控范围。7.3 清楚“自顶向下”和“自底向上”两种动态规划写法动态规划是递归和递推最重要的应用场景。初学者可以从“记忆化递归”入门逐步过渡到“递推填表”因为两者解决的问题完全一样只是方向不同。举个例子。求斐波那契数列记忆化递归是“自顶向下”从F(n)开始逐步向F(1)、F(2)递归。数组递推是“自底向上”先从F(1)、F(2)开始逐步计算到F(n)。自顶向下写法的优点是状态转移逻辑更贴近人类思考缺点是函数调用有开销、容易写出过深的递归。自底向上的写法更适合严格依赖顺序填表的题目代码更接近动态规划的最终形态。两种写法都值得练习不要只依赖其中一种。7.4 做好边界测试和调用深度的保护递归函数交付前至少要测试这四类数据最小输入比如 n0、n1、n2。边界输入比如数组长度刚好等于递归边界。负数或不合法输入确认函数不会无限递归。最大规模输入观察是否会栈溢出或超时。如果递归函数用于对外接口建议在函数入口处用参数校验兜底。例如求阶乘时如果传入负数可以先提示参数错误。在算法竞赛里虽然不要求这么严谨但在工程代码里任何来自外部的输入都应当默认是不可信的。7.5 给“学不会”的你一条可执行路线如果你现在看到“递归”两个字还是有点慌不要急着找一堆难题刷按下面的路线走会更稳用笔在纸上推导斐波那契递推式的前几项。写完数组递推再用滚动变量优化。把阶乘递归、斐波那契递归各敲三遍直到能徒手写出来。给递归函数加打印观察进入和退出顺序。做“整数转字符串”和“汉诺塔”两道题体会递归顺序控制。尝试解决二叉树的前序、中序、后序遍历理解递归在数据结构中的应用。学习“递归 缓存 记忆化搜索”再过渡到动态规划。如果每一道经典题都亲手运行过你会在某个瞬间发现递归不再是“玄学”它只是一种分解问题的工具而递推公式就是描述如何分解的数学语言。建议把本文涉及的代码保存到一个项目文件夹里方便以后复习。如果你在运行中遇到和文章不同的报错欢迎在评论区把错误现象发出来大家一起排查。