★ FEATURED ARTICLE “递归”这个词我最早听到时以为是某种高深到劝退的魔法直到开始“我爱学算法”系列打卡真正静下心啃了两周才发现它其实只是“函数自己调用自己”这么一件事。但千万别小看这件事从阶乘、斐波那契到二叉树遍历、全排列、回溯、分治几乎所有稍微有点技术含量的算法题里都有它的影子。它能解决的问题都有一个共同特征结构重复、规模递减最后在某个不能再拆的边界停下。这篇笔记想把我学习递归时的完整复盘写出来既给正在卡递归的初学者指个方向也给已经会写递归但总怕用错的人梳理一下底层机制。1. 为什么要学递归它到底解决什么问题1.1 递归不是炫技是“大事化小”的思考方式我以前写过一段遍历文件夹的代码用循环实现需要手动维护一个栈每遇到一个子目录就往栈里压还得小心处理访问顺序写着写着就容易乱。后来换成递归每个目录的处理逻辑完全一样先读当前目录遇到子目录就调用自己。十几行代码缩成几行逻辑一眼就能看明白。这就是递归的真实价值它不负责提升运行速度也不负责让代码看起来高深它负责把“重复嵌套且未知深度”的问题变成“遇到同样类型的问题就用同样的解法”这种自然表达。你可以把递归想象成剥洋葱。你永远不知道一颗洋葱有多少层但你处理的每一层动作都是一样的剥掉一层外皮然后对剩下的洋葱继续执行同一个动作。当洋葱剥到最里面没有皮可剥时动作停止然后你一层层把剥好的皮叠回去。这个“剥到最内层再逐层返回”的过程就是函数调用自己再不断回溯的过程。另一个更贴切的类比是俄罗斯套娃。打开一个套娃里面还是一样的套娃你只能一个接一个地打开直到最小的那个不能再打开。递归程序做的事情就是不停地打开比自己小一号的套娃直到边界条件出现。1.2 什么样的题目会让我立刻联想到递归刷题多以后我对题型有了点感觉。下面这几类信号一出现我第一反应就是往递归想问题可以被拆成若干个和原问题结构相同、规模更小的子问题。比如“计算 n 的阶乘”可以拆成“计算 n-1 的阶乘再乘以 n”子问题和原问题完全同构。数据本身具有递归定义。比如二叉树一个节点有左子树和右子树而子树仍然是二叉树链表去掉头节点后剩下的部分仍然是一个链表。需要遍历所有可能路径或组合比如全排列、组合、岛屿数量这类搜索问题本质是一棵隐式的决策树树的结构非常适合递归。问题规模和你传入的参数有关并且每一层调用都在让参数向终止条件靠近。这种“参数递减”的特征是递归能正确收敛的基础。我印象很深的一道题是“反转链表”。用循环写需要三指针边遍历边改 next一不留神就断链。用递归写你只需要考虑如果当前节点后面已经是一个反转好的链表那我把当前节点的 next 指向新链表尾部就行。这个“假设子问题已经解决”的思维方式比手动操作指针要舒服得多。1.3 递归和数学归纳法是一对孪生兄弟我发现很多同学写递归最大的障碍是不敢“假设子问题已经对了”。这种担忧其实多余因为递归的数学根基就是数学归纳法。数学归纳法证明一个命题 P(n) 成立分两步先证明 P(1) 成立再假设 P(k) 成立并证明 P(k1) 成立。递归代码也是一样先写终止条件这是“基础情形”再写递推关系这是“归纳步骤”。用阶乘来对照。证明“阶乘可以这样算”时你只要说明1! 1并且假设 (n-1)! 已经能算出来那么 n! n * (n-1)! 也一定能算出来。递归代码完全照搬这套逻辑。所以我在写递归前习惯先在草稿纸上写出两样东西终止条件是什么以及规模为 n 的计算如何通过规模为 n-1 的计算来表达。这两样写清楚代码几乎就是照着抄。2. 递归的第一性原理三件套与调用栈2.1 写递归前先明确三件事很多人一上来就埋头写代码写着写着就死循环。我自己的做法是先回答三个问题终止条件是什么也就是参数满足什么条件时函数直接返回结果不再调用自己。函数需要哪些参数、返回值是什么参数要能体现规模变化返回值要能供上层函数使用。本轮调用做了什么它如何把问题变小并把递归调用的结果组合成自己的结果拿阶乘来说def factorial(n): if n 1: return 1 return n * factorial(n - 1)这里终止条件是 n 1返回 1参数是 n返回值是整数本轮做的事是“让下一层算 (n-1)!再用 n 乘上这个结果”。三个问题对应三行关键代码结构极其清晰。我见过不少新手在 n 0 和 n 1 之间纠结。其实不用纠结只要保证终止条件里的返回值能让递推公式正确闭合就行。你甚至可以写 n 1: return 1覆盖面更广。2.2 递归在内存里到底发生了什么理解递归必须理解调用栈。每次函数调用系统都会在内存栈里压入一个栈帧里面保存着这次调用的参数、局部变量以及函数返回后要执行的代码位置。递归调用也不例外只不过每次调用的是同一个函数名但参数不同。我用“叠盘子”来记这个过程第一次调用 factorial(4)相当于在桌上放了一个盘子里面调用 factorial(3)又在上面放一个盘子一直放到 factorial(1)发现不用再放了就开始一层层往回拿盘子。每一层拿到下一层返回的结果结合自己的局部变量做计算再返回给上一层。所以递归的执行并不是“一口气从 4 算到 1”而是先一路展开到边界再一路收回来。“递”是不断调用自己把问题推得更小“归”是结果一层层向上返回。这两个字拆开理解你就会明白为什么递归体里写的 print 语句有时会从里往外打印。2.3 漏掉终止条件会发生什么如果递归函数缺少终止条件它就会无限地调用自己调用栈不断增高最终把内存栈撑爆程序直接崩溃。这通常就是面试时大家常说的栈溢出Stack Overflow但注意它不一定是指刷题网站上的那个提问社区而是真实的内存错误。不同语言对栈深度的限制不一样。Python 默认递归深度限制大概在 1000 层左右C 则主要看系统分配的栈大小通常是几 MB调用过深同样会爆。有个常见误区觉得只要用sys.setrecursionlimit(1000000)把 Python 的递归深度调大就能解决一切问题。我一开始也这么干过后来发现只是延迟了崩溃时间因为系统内存是有限的栈帧又不是免费的。调大递归限制只适合那些确实需要一定深度但又不至于爆内存的场景真正的无限递归靠调参数永远救不回来。3. 从经典题目学递归代码怎么写才不飘3.1 阶乘最朴素的入口阶乘是递归的“Hello World”因为它的递推关系几乎透明。接着上一节的代码我带你走一遍 factorial(4) 的展开过程def factorial(n): if n 1: return 1 return n * factorial(n - 1)执行 factorial(4) 时函数先判断 4 不等于 1于是计算 4 * factorial(3)。为了得到 factorial(3)又去计算 3 * factorial(2)接着是 2 * factorial(1)。到 factorial(1) 时直接返回 1。然后 factorial(2) 得到 2 * 1 2factorial(3) 得到 3 * 2 6factorial(4) 最终得到 4 * 6 24。如果你想更直观地看这个过程可以在每个函数入口和出口打印日志。我调试时常常这样做后面专门讲调试技巧。阶乘虽然是基础题但它把递归的“展开与回归”演绎得明明白白值得亲手跑一遍。3.2 斐波那契递归最典型的陷阱斐波那契数列的递归写法几乎是标准答案def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)代码简洁但性能吓人。fib(5) 会去计算 fib(4) 和 fib(3)fib(4) 又会去计算 fib(3) 和 fib(2)同一个 fib(3) 被算了两次。随着 n 变大重复计算量指数级增长fib(30) 已经慢得能明显感觉到卡顿fib(40) 在没有优化的情况下可能要算好几秒。我把 fib(6) 的递归调用树画在纸上后发现这棵树几乎是一个满二叉树节点数大约是 2^n 级别的数量。所以斐波那契是理解“递归不总是好方案”的绝佳例子。它告诉我递归写起来快但得看清楚是否存在大量重叠子问题如果有就要考虑优化手段后面第 4 节会详细展开。3.3 汉诺塔找到最小操作单元汉诺塔是我学递归时最震撼的一道题。问题是有三根柱子 A、B、CA 上有 n 个大小不同的盘子大盘在下、小盘在上要求全部移到 C 上每次只能移动一个盘子且任何时候大盘不能压在小盘上。第一次看到这个问题我觉得需要精确规划每一步结果网上那段只用了三行递归的代码让我彻底破防def hanoi(n, src, dst, aux): if n 0: return hanoi(n - 1, src, aux, dst) print(fmove disk from {src} to {dst}) hanoi(n - 1, aux, dst, src)它的思路是把前 n-1 个盘子从 A 借助 C 移到 B然后把第 n 个盘子从 A 移到 C最后把 B 上的 n-1 个盘子借助 A 移到 C。三个步骤里第 1 步和第 3 步其实是同一个“移动 n-1 个盘子”的子问题只是柱子角色不同。递归思考汉诺塔的关键是别去追每一个盘子的移动细节。你只需要相信如果我能把 n-1 个盘子按要求移走那么 n 个盘子的问题就只剩下把底盘搬过去再把 n-1 个盘子搬回来。这种“向下信任”的心态也是学递归必须跨过的一道坎。3.4 树的遍历递归最舒服的应用场景二叉树是递归定义的数据结构所以用递归遍历树几乎是天作之合。前序遍历的代码长这样class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def preorder(root): if root is None: return print(root.val) preorder(root.left) preorder(root.right)中序和后序只是把 print 的位置换一下放在左递归之后或右递归之后。每次调用只处理当前节点并把左右子树当成一棵新的树递归处理。树的递归遍历让我体会到当数据结构和算法的思维方式一致时代码会变得极具表现力。同时也要注意树递归同样有深度风险。如果树退化成链表递归深度会等于节点数极端情况下可能栈溢出。这种时候可以考虑显式栈迭代不过这是后话。4. 递归的复杂度分析与性能优化4.1 时间复杂度先画递归树学递归不能只看代码能不能跑还得知道它跑多快。我常用的方法是画递归树把每一次递归调用当成一个节点边表示调用关系然后数节点。阶乘是单链递归调用链长度是 n每次调用做 O(1) 工作所以复杂度 O(n)。斐波那契是二叉递归每个节点分裂成两个树高 n节点数约 2^n复杂度 O(2^n)。这就是为什么它慢。归并排序则不同每次把问题分成两半递归深度 log n每层需要合并两个有序序列总工作量 O(n)所以总复杂度 O(n log n)。如果见到更复杂的形式比如 T(n) 2T(n/2) n可以用主定理估算。主定理听起来吓人其实就三句话看 n 和 f(n) 谁更有话语权。但刷题阶段碰到最多的还是上面三种形态先把递归树画熟比背主定理更实用。4.2 空间复杂度别忽略栈深度递归的空间复杂度不是 O(1)而是 O(递归深度)。因为每一层调用都要在系统栈里占用一个栈帧直到该层返回才释放。阶乘递归深度是 n所以空间 O(n)。二叉树遍历如果树深度是 h空间就是 O(h)。归并排序递归深度 log n空间 O(log n) 加上合并时的临时数组 O(n)通常我们说是 O(n)。为什么这个容易忘因为很多人只看时间不看空间。但真到了内存受限的嵌入式环境或追求极致性能的底层系统递归深度过大就是一个实实在在的隐患。所以至少要知道递归的“隐形成本”是栈空间。4.3 性能优化三板斧备忘录、尾递归、循环改写斐波那契这种重复计算问题第一个优化思路是加备忘录。把已经算过的结果存起来下次直接查表def fib_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 1: return n memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo) return memo[n]加了这层缓存每个 n 只算一次时间复杂度从 O(2^n) 降到了 O(n)。这就是记忆化搜索也是动态规划自顶向下写法的雏形。第二个优化是尾递归。如果函数在返回前做的最后一件事就是递归调用而且没有任何额外的计算这个调用就是尾调用。部分编译器会把尾调用优化成循环从而不增加栈深度。比如阶乘的尾递归版本def factorial_tail(n, acc1): if n 1: return acc return factorial_tail(n - 1, acc * n)这里的关键是参数 acc 一直在累积结果等递归到边界时直接返回 acc不需要再回上一层做乘法。可惜的是Python 官方解释器并不做尾递归优化所以这个写法在 Python 里只是看起来更优雅栈深度该涨还是涨。但在支持尾调用优化的语言里这是一种很重要的写法。第三个思路更直接很多递归问题都能改写成循环。斐波那契可以用两个变量滚动更新def fib_iter(n): a, b 0, 1 for _ in range(n): a, b b, a b return a循环版本没有栈空间效率也高。能改循环就改循环改不了就考虑用显式栈模拟递归这也是面试中经常考察的能力。5. 高频考点回溯、DFS与分治的底层都是递归5.1 全排列递归加状态标记全排列是回溯算法的入门题。要列出数组 [1,2,3] 的所有排列本质上就是构建一棵决策树第一个位置可以选 1、2、3选完以后第二个位置只能从剩下的数里选。决策树某个分支走到底就是一个完整的排列。回溯的标准写法如下def permute(nums): res [] used [False] * len(nums) def dfs(path): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs(path) path.pop() used[i] False dfs([]) return res这里有两个关键动作递归前“做选择”递归后“撤销选择”。撤销选择非常重要否则下一轮循环会看到错误的状态。我刚开始经常忘记 path.pop() 和恢复 used结果排列结果大得离谱或者一堆重复。全排列这类题目教会我一个通用模板递归函数里先判断是否到达终点然后遍历可选的下一步对每个选择做标记、递归、再撤销标记。这个模板套到组合、分割、棋盘类问题上大多都能用。5.2 二分查找递归和迭代的边界差异二分查找通常用迭代但递归版本对理解区间边界特别有帮助def binary_search(nums, target, lo, hi): if lo hi: return -1 mid (lo hi) // 2 if nums[mid] target: return mid if nums[mid] target: return binary_search(nums, target, lo, mid - 1) return binary_search(nums, target, mid 1, hi)终止条件是 lo hi表示区间已经为空。然后根据中间值和目标值的大小关系把区间缩小一半递归处理剩下的一半。这个例子提醒我递归终止条件不一定是“等于某个数”也可能是“区间失效”。写递归时一定要反复确认终止分支是否覆盖了所有边界情况。二分搜索里如果写成 lo hi 再接 nums[mid] target 的判断虽然也能做但边界会更绕新手特别容易差一错误。5.3 分治算法递归加合并结果分治算法是一种思想递归是它的实现载体。分治三步骤分解、解决、合并。归并排序就是最经典的代表def merge_sort(nums): if len(nums) 1: return nums mid len(nums) // 2 left merge_sort(nums[:mid]) right merge_sort(nums[mid:]) return merge(left, right)分解是把数组切两半解决是递归把两半各自排好序合并是把两个有序数组合并成一个。归并排序的时间 O(n log n)而且我写对 merge 函数比写递归本身更费劲。这不算意外因为分治最难的往往不是递归而是“合并”这一步如何处理两侧子问题的结果。从归并排序里学到的通用原则是设计递归函数之前先明确这个函数返回什么、需要什么参数然后在假设子问题已经正确解决的基础上专注当前这一层的合并逻辑。一旦想通了递归的壳子就是一层薄薄的包装纸。5.4 动态规划与递归的记忆化动态规划题里有一类经典做法是先写暴力递归再加备忘录最后改成递推。比如“爬楼梯”问题每次可以走 1 阶或 2 阶问 n 阶有多少种走法。暴力递归直接模仿斐波那契def climb(n): if n 2: return n return climb(n - 1) climb(n - 2)然后加 memo 字典就变成记忆化搜索。接着你会发现它本质上就是斐波那契可以用自底向上的递推重写。这条路几乎是递归和动态规划之间最顺的一座桥。所以学递归不是学一个孤立的知识点它是理解动态规划、回溯、分治、DFS 的共同基础。我在刷题时先写递归再逐步优化思路往往比一上来直接写动态规划更清晰。6. 我踩过的坑与调试技巧6.1 常见错误清单我把递归最常踩的坑整理成一张速查表每次写递归前扫一眼能省很多 debug 时间。错误类型具体表现原因解决办法漏写终止条件栈溢出或死循环函数没有出口先写边界分支终止条件写错结果偏大/偏小或者边界输入崩溃比如 n 0 写成 n 1用 0、1、空输入单独测试参数没有向边界靠近无限递归递归调用时传了 n1 或原样传 n确认每层都缩小问题规模忽略递归返回值函数返回 None递归调用的结果没有参与计算搞清楚返回值怎么用回溯没撤销选择结果重复或状态错乱递归结束后忘记恢复标记递归后立即逆操作栈溢出递归深度过大数据规模超出栈深度限制考虑循环、显式栈或尾递归我最常犯的是第一条和第四条。刚学递归时一个函数写了半天没 return打印却能看到值最后发现递归分支跑完没有把结果传回来。这种问题靠眼睛不容易发现最好配合下面说的打印调试。6.2 用打印观察递归执行过程遇到递归想不通我的习惯是加一个 depth 参数控制缩进把每次进入和退出的信息打印出来def factorial_trace(n, depth0): print( * depth f call factorial({n})) if n 1: print( * depth base case return 1) return 1 res n * factorial_trace(n - 1, depth 1) print( * depth f return {res}) return res factorial_trace(4)运行后你能清楚看到每一层的参数、哪一层到达终止条件、结果又是怎么一层层传回去的。这是我理解递归最有效的手段。调试树形递归比如全排列我更推荐把“当前路径”打出来再配合 used 数组一起看。这样能看出某个分支什么时候进入、什么时候回溯。等确认思路正确后再把所有调试打印删掉千万不要留在正式提交的代码里。6.3 怎么训练递归思维如果看完这篇文章还是觉得递归很抽象我的建议是分四个阶段来练第一阶段默写三件套。面对一个递归题先不着急写逻辑先写出终止条件、函数参数和返回值、本轮怎么缩小规模。写不出来就说明题目还没理解透。第二阶段用数学归纳法验证。思考“如果规模为 n-1 的版本是对的规模为 n 的这个步骤能不能把它变成对的”能就大胆写递归不能说明你的递推关系有问题。第三阶段小数据手动模拟。拿 n3n4 这种小规模输入在纸上画出递归树核对返回值。这个方法虽然慢但对建立直觉帮助极大。第四阶段大量刷题。树的前中后序遍历、链表反转、判断二叉树是否对称、全排列组合、子集、岛屿数量、括号生成这些都是经典递归题。每道题都先写递归能写出来后再想能不能优化成迭代。我个人最受用的一个心理技巧是写递归时不要试图跟踪每一层具体怎么操作。你只需要确认两件事——最底层的返回是对的以及当前层根据子问题的结果做计算是对的。剩下的事情计算机比你可靠得多。这个心态一旦建立递归就从“玄学”变成了“工具”。最后再分享一个小技巧如果某道题你实在想不出终止条件可以先把问题规模取最小的情况例如 n0 或空数组思考这时候答案应该是什么那个答案往往就是终止条件。这个办法我用了很久几乎每次都能帮我打开思路。递归不像有些算法那样偏重套路记忆它更像一种看问题的方式找到最小单元相信子问题然后大胆调用自己。希望这篇复盘能让你少走一点我走过的弯路。
阅读完成 · 觉得有帮助？
