递归与递推可能是从“能刷简单题”到“能写中等题”之间最大的一道坎。很多人能看懂斐波那契的递推公式但真让自己写一个递归函数就不知道 return 该放在哪里更常见的是题目一改、递归层数一变程序直接栈溢出。这次我们聊的不是某个显存要求很高的新模型而是一套算法学习方法论。简单说就是用“数列 → 递推 → 递归 → 记忆化 → 递推优化”这条主线把递归和递推一次吃透。老书难找也没关系真正值钱的是它背后的思考顺序先看初值再找关系最后选实现方式。这套顺序放到今天依然实用尤其适合准备 CSP、考研数据结构、刷 LeetCode 的人。我会用斐波那契数列、整数转字符串、汉诺塔、全排列、二叉树遍历这五个例子把递归展开成“从终止条件到递推步”的完整链路再给你一套防爆栈、防超时、防边界写错的排查清单。读完你能跑通的可执行代码示例也能源码级理解递归为什么慢、递推为什么快。1. 核心概念速览先建立一个总表把后面所有讨论都挂到这组概念上。下面这些术语经常混着用但严格来说并不同。概念核心数学表达程序视角数列按顺序排列的一列数a1, a2, a3, ...数组、列表、生成器递推公式后一项与前几项的关系an f(an-1, an-2)状态转移方程递推从初值开始向后逐步计算已知 a1算 a2再算 a3for / while 循环递归函数调用自身先展开再回归f(n) 调用 f(n-1)递归函数 调用栈递归基终止条件最小子问题不再调用自身n1 时直接返回if 判断后的 return递归步把大问题缩小并处理返回值f(n) f(n-1) 1return f(n-1) 1记忆化把已计算子问题存起来查表代替重复计算字典 / 数组缓存动态规划用递推关系和状态数组求解dp[n] dp[n-1] dp[n-2]重叠子问题 无后效性几个容易混淆的判断递推是“从小到大”的解决问题方式先有底盘再造高楼。递归是“从大到小”的拆解方式先把大任务拆到不可拆再逐层返回。一个递推式可以写成循环也可以写成递归。反过来一段递归并不总能轻松改成递推尤其是处理树、图这类递归结构时。所以本文的目的不是让你只学会其中一种而是在两种写法之间自由切换。2. 这套方法适合谁能解决什么问题如果你正处于下面几个场景这套训练思路会非常直接刚开始学算法看到“递归”两个字就发怵不知道函数怎么调用自己。准备 CSP-J/S、NOI 系列比赛初赛考概念复赛考代码递归递推都是高频考点。准备考研计算机或面试算法题二叉树、回溯、分治全部依赖递归思维。刷题时经常写一个递归版本然后超时改成 DP 又不知道从哪下手。它能帮你解决的问题包括写递归时不再漏终止条件能预判递归会不会爆栈能用“记忆化搜索”救活一个朴素递归能把一个递推式从递归形式平滑改写成迭代形式。同时也要说清楚边界真实生产环境里如果递归深度可能达到几千层甚至几万层必须谨慎。Python 默认递归深度在 1000 左右C 的调用栈资源也不是无限的。工程上遇到深层递归通常会改写成显式栈或循环而不是硬调递归上限。递归是工具不是万能药。3. 从数列递推公式到程序语言先把数学公式翻译成人脑步骤先看最经典的斐波那契数列。数学上可以写F(0)0, F(1)1, F(n)F(n-1)F(n-2)这个递推公式描述的是“某一项和它前面两项之间的关系”。但计算机没有“数学直觉”它只能一步一步执行。所以拿到递推公式后第一件事是把它翻译成人能复述的步骤。比如想知道 F(5)人脑的展开过程是F(5) F(4) F(3) F(4) F(3) F(2) F(3) F(2) F(1) F(2) F(1) F(0) F(1) 1 F(0) 0一直拆到 F(0) 和 F(1) 这两个不能再拆的“已知项”然后开始回代F(2) 1 0 1 F(3) 1 1 2 F(4) 2 1 3 F(5) 3 2 5注意“拆开”和“回代”这两个动作正是递归的运行过程。如果不想拆开直接顺着算那就用循环递推。用 Python 写一个从 F(0)、F(1) 开始向后推的版本def fib_iter(n: int) - int: if n 0: raise ValueError(n must be 0) if n 0: return 0 a, b 0, 1 # a 表示 F(n-2)b 表示 F(n-1) for _ in range(2, n 1): a, b b, a b return b for i in range(11): print(fF({i}) {fib_iter(i)})运行后输出F(0) 0 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这就是递推从边界条件出发用已知项计算未知项像滚动数组一样不断向前推进。这里只有两个临时变量 a 和 b空间开销极小。4. 递归代码如何执行栈、调用帧与终止条件同样是斐波那契很多人一眼会写出递归版def fib_rec(n: int) - int: if n 0: return 0 if n 1: return 1 return fib_rec(n - 1) fib_rec(n - 2)代码很短问题是你真的理解它怎么跑吗调用 fib_rec(5) 时Python 会先为 fib_rec(5) 创建一个调用帧这个调用帧发现要计算 fib_rec(4) fib_rec(3)于是先调用 fib_rec(4)再创建新的调用帧…… 直到 fib_rec(1) 和 fib_rec(0) 直接返回值调用帧才开始一个个释放。整个过程由系统栈管理先进后出。函数调用帧里保存了什么局部变量、参数、返回地址。所以每递归一层就会在内存栈上多占一块空间。层数太深栈空间耗尽就会出现 RecursionError 或 C 里的栈溢出。写递归要先回答三个问题终止条件是什么必须存在一个或多个最小问题不需要再次调用自身。每次递归是否让问题变小比如 n-1、n//2、删除一个节点、缩小数组区间。返回值如何组装很多时候递归卡住不是因为你不会调用而是不知道 return 后面应该怎么拼。一个最简单的错误示范def forever(): return forever()调用 forever() 会不断创建调用帧最终抛出 RecursionError。看起来夸张但很多人写递归时实际上做过类似的事递归条件前进方向写错了、参数没更新、终止条件判断放在了递归调用之后于是程序直接跑飞。递归一定要有“收口”的动作也就是递归基。对于树遍历收口是空节点对于整数递归收口是个位数对于排列回溯收口是路径长度等于总长度。5. 从递归到递推再到底层优化拿斐波那契开刀斐波那契是理解递归超时最典型的案例。朴素的 fib_rec 看起来干净它的问题在于同一子问题被反复计算。fib_rec(5) 需要 fib_rec(4) 和 fib_rec(3)fib_rec(4) 又需要 fib_rec(3) 和 fib_rec(2)。fib_rec(3) 被计算了两次fib_rec(2) 被计算了三次。当 n 变大重复规模指数级上升。第一步用记忆化缓存解决重复计算。memo {0: 0, 1: 1} def fib_memo(n: int) - int: if n in memo: return memo[n] memo[n] fib_memo(n - 1) fib_memo(n - 2) return memo[n]也可以用 Python 自带的 lru_cachefrom functools import lru_cache lru_cache(maxsizeNone) def fib_memo_lru(n: int) - int: if n 0: return 0 if n 1: return 1 return fib_memo_lru(n - 1) fib_memo_lru(n - 2)两步改造逻辑先查缓存缓存里有就直接返回。缓存里没有递归计算结果写回缓存。这样每个 n 只计算一次时间复杂度从指数级降到 O(n)。第二步从记忆化递归改成显式递推。记忆化递归是自顶向下递推是自底向上。def fib_dp(n: int) - int: if n 0: return 0 if n 1: return 1 dp [0] * (n 1) dp[0] 0 dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这个版本把每一项的状态都保存在数组里方便后续读取。如果不需要保存所有项还能继续压缩成两个变量也就是前面的 fib_iter。三种解法对比解法时间复杂度空间复杂度需要注意的问题朴素递归O(2^n)O(n) 递归栈n 稍大就超时或卡死记忆化递归O(n)O(n) 缓存 O(n) 栈缓存命中思路要清晰递推 DPO(n)O(n) 或 O(1)边界初值别写错很多初学者以为“递归优化”就是把递归改成循环实际上真正重要的是先找到重叠子问题。找到之后用记忆化能保留递归结构用递推能进一步压缩空间。两者不是互相排斥的关系。6. 经典题型拆解与代码验证光讲理论不够。下面这几个例子覆盖了从“数列递归”到“结构递归”再到“回溯递归”的基本形态。6.1 整数 n 转换成字符串递归基和拼接思路经典题目“递归法将一个整数 n 转换成字符串”也是很多课程喜欢考的递归入门题。题目要求不直接调用 str()而是递归地把数字逐位拆开。比如输入 1234输出字符串 1234。思路1234 去掉最后一位是 123可以递归处理123 再去掉最后一位是 12继续递归12 再去掉一位是 11 是最后一位直接返回字符 1。从最外层返回时再逐层拼接个位字符。def int_to_str(n: int) - str: if n 0: return - int_to_str(-n) if n 10: return chr(ord(0) n) return int_to_str(n // 10) chr(ord(0) n % 10) print(int_to_str(1234)) print(int_to_str(0)) print(int_to_str(-567))运行结果1234 0 -567这个题的要点是递归基是 n 小于 10直接返回这一位递归步是先把 n//10 转成字符串再接上 n%10 对应的字符。如果把递归调用放在拼接之后或者没有处理负数结果就会错。另有一个变体版本是“倒序输出整数各位”这时递归方向和控制台输出时机又不一样建议自己把两个版本对比着写一遍。6.2 汉诺塔找到 n 和 n-1 的关系汉诺塔是所有递归题里最“反递推”的例子。递推公式 T(n)2T(n-1)1 能快速算出移动次数但如果你想用循环直接模拟每一步搬运反而很难写。递归写法就非常自然。def hanoi(n: int, source: str, target: str, auxiliary: str) - None: if n 1: print(f{source} - {target}) return hanoi(n - 1, source, auxiliary, target) print(f{source} - {target}) hanoi(n - 1, auxiliary, target, source) hanoi(3, A, C, B)输出正好是 7 行A - C A - B C - B A - C B - A B - C A - C递归逻辑可以概括为三步先把上面 n-1 个盘子从 source 移到 auxiliary。把最大一个盘子从 source 移到 target。再把 n-1 个盘子从 auxiliary 移到 target。不要试图在脑子里完整模拟每一步盘子位置变化你要做的是相信“把 n-1 个盘子搬走”的子任务能被同一条递归函数完成。这也是递归思维的训练目的。6.3 全排列递归树与回溯全排列是 DFS 回溯的入门题也是 CSP 复赛搜索题的常见模板。def permute(nums): result [] path [] used [False] * len(nums) def dfs(): if len(path) len(nums): result.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] True path.append(x) dfs() path.pop() used[i] False dfs() return result print(permute([1, 2, 3]))输出[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]这里递归基是 path 长度等于 nums 长度递归步则是在每一层尝试所有“还没用过”的数字。递归调用后马上撤销选择这就是回溯。全排列的数量是 n!所以当 n 增大到 10 以上搜索空间会迅速膨胀。做题时要先估算 n 的大小避免盲目递归。6.4 二叉树遍历递归最适合的“同构子问题”二叉树天然适合递归因为左右子树和原树结构相同。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def inorder(root): if root is None: return [] return inorder(root.left) [root.val] inorder(root.right) root TreeNode(1) root.right TreeNode(2) root.right.left TreeNode(3) print(inorder(root))输出[1, 3, 2]树递归只需要考虑“空节点怎么返回”和“当前节点和子树结果怎么拼”。如果空节点返回 None再调用 None.left 就会报 AttributeError。所以递归基要放在函数第一行保证调用递归前先判断是否为空。7. 性能、内存与复杂度观察递推和递归的真正差异不只在写法上还体现在运行时间和内存占用上。递归版本每次函数调用都会有额外开销。Python 的函数调用开销尤其明显。朴素递归 fib_rec 在 n35 左右就已经能感受到明显延迟到 n40 会非常慢。递推版本算 n100000 也没有压力前提是只保留最后结果而不存储整个大列表。如果需要在递归里观察资源占用可以在函数入口打印参数和当前递归深度def debug_rec(n, depth0): print( * depth fenter n{n}) if n 1: print( * depth fbase {n}) return n result debug_rec(n - 1, depth 1) debug_rec(n - 2, depth 1) print( * depth fresult {n} {result}) return result print(debug_rec(4))输出能清楚看到展开顺序和重复子问题缺点是输出量很大只适合小 n 调试。关于递归深度Python 默认大约在 1000 左右。可以查看import sys print(sys.getrecursionlimit())但修改递归上限需要谨慎。把系统递归上限调到 100000 不代表程序内存就装得下栈帧占用是实打实的。生产代码遇到深度遍历优先考虑用显式栈模拟递归def fib_stack(n: int) - int: if n 0: return 0 if n 1: return 1 stack [(n, False)] values {} while stack: num, visited stack.pop() if num 0: values[num] 0 elif num 1: values[num] 1 elif not visited: stack.append((num, True)) stack.append((num - 1, False)) stack.append((num - 2, False)) else: values[num] values[num - 1] values[num - 2] return values[n]这段代码把系统调用栈换成了程序自己控制的栈思路并不复杂但能避免深递归的 RecursionError。8. 常见问题与排查方法问题现象可能原因排查方法解决方案报 RecursionError递归没有终止条件或递归深度过大检查递归函数开头是否有 base case打印参数变化补终止条件改用显式栈或递推程序无输出/卡死递归调用参数没减小形成死循环在函数入口打印 n看是否一直不变修正递归步的参数推进结果始终多 1 或少 1递推数组索引和项数不对齐用纸笔列出 n0,1,2,3 的期望值统一初值定义dp[0] 还是 dp[1] 开头递归结果正确但超时存在大量重复子问题用计数器统计某个子问题调用次数加 memo 缓存或直接改递推递推时数组越界循环边界超过数组长度检查 list 长度和 for i in range 的范围确认 dp 数组长度是 n1递归处理负数崩了没有处理输入小于 0 的情况测试负数输入在递归入口先做负数归一化二叉树递归报 None 属性错误对空节点调用了 .left 或 .val看报错行是否在递归函数里递归函数最前面加 if root is None: return回溯结果全是空列表直接把 path 追加进 result后续修改影响全部检查 result.append 的参数是否拷贝使用 path[:] 或 list(path) 深拷贝最稳妥的调试顺序是拿一个极小的输入比如 n3手写出展开过程。在函数入口打印当前参数验证递归是否逐步逼近终止条件。只修改一个变量比如缓存、边界、递归方向不要同时改多个。确认终止条件在最前面执行不能被其他代码挡住。9. 系统训练路线与最佳实践光看完这篇文章不够真正吃透需要按下面这套路线走一遍。第一轮纸笔推数列找 10 道递推题先不用电脑。题目给出递推式后自己在纸上列出前 10 项标出初值和递推关系。这一步是训练“从公式到具体数值”的敏感度。第二轮写暴力递归把纸上的递推式翻译成递归函数输入小数据验证是否能得到纸上的前几项。这一轮不追求性能只追求“递归基正确”和“return 回代正确”。第三轮加速优化观察递归调用中是否存在重复子问题。如果有先加记忆化再尝试改递推。没有重复子问题的递归比如遍历二叉树一般不需要改成递推。第四轮换应用场景去 LeetCode 或 CSP 题库中找这些典型题练手青蛙跳台阶 / 爬楼梯线性递推入门。整数 n 转字符串递归与拼接。汉诺塔递归分治。归并排序递归处理区间合并结果。二叉树前序、中序、后序遍历结构递归。二叉树的最大深度递归返回值。全排列、子集、组合递归与回溯。反转链表递归处理子结构。简单动态规划一维 DP、二维 DP。第五轮形成自己的“五步法”遇到一道能用递推动态的题按下面顺序走明确状态含义。比如 dp[i] 表示第 i 项的结果。写出递推关系。dp[i] 和 dp[i-1]、dp[i-2] 有什么关系。确定边界初值。dp[0]、dp[1] 等于多少要核对题目下标从 0 还是 1 开始。选择实现方式。递归清晰就用递归递归会爆栈或超时就换记忆化或递推。检查空间优化。是否能用两个变量代替整个数组。老书和新资料的最大差别不是知识量而是它会要求你把每一步都落实在纸面上。如果你现在看到递推式第一反应是“哦这个我会”但关上文章后写不出斐波那契递归更不会改成滚动变量版本那就回到第三轮把手上的递推式再抄一遍、跑一遍。递归不是玄学是一套可以肉眼观察的栈操作递推也不是套路是从小到大逐步填表的过程。下一次做题时先问自己这个问题能列出递推公式吗如果能尝试先用小样例跑一个最笨的递归再考虑加缓存、改递推。这一套训练跑完你会明显感觉到递归的恐惧感降低了。建议把本文中斐波那契、整数转字符串、汉诺塔三个代码自己重写一遍再去找两到三道动态规划题做递推改造。递归递推系统吃透后二叉树、搜索、动态规划都会轻松很多。