先说一个我见过太多次的场面有人在草稿纸上把递归的调用过程一层一层画了半个小时觉得自己懂了一上手写 LeetCode 上的反转链表返回值还是空的或者直接报栈溢出。递归这个知识点在简单题里出现的频率高得离谱——树的遍历、链表操作、二分查找、快速幂几乎都是它的地盘。它不像双指针那样看一眼就会也不像动态规划那样一上来就劝退它卡在中间属于看别人的题解两分钟就懂自己写十分钟写不出来的典型。这一讲我按零基础的角度把简单递归彻底拆开递归到底由哪几个零件组成、调用栈在背后干了什么、简单题里最常见的几类递归模板长什么样、写挂了应该按什么顺序排查、以及练题的节奏怎么安排。目标是让你看完之后能独立写出反转链表、二叉树最大深度、二分查找这些题的递归版本而不是把题解背下来。前置要求很低会写 for 循环、会定义函数就够了不需要额外的数据结构基础。1. 先把递归就是函数调用自己这句话纠正过来1.1 自我调用只是形式降级问题才是核心绝大多数教材对递归的定义是函数直接或间接调用自身这句话本身没错但它只描述了语法现象没有描述思维过程。真正决定你能不能写对递归的是另一件事你有没有把原问题准确地降级成一个规模更小、但结构完全相同的子问题。拿反转链表举例。很多人第一反应是我要从头到尾把指针全部翻过来于是开始写循环、存临时变量。这当然能做出来但那是迭代思维。递归思维是这样一句话如果 head 后面的那一段已经反转好了我该怎么把 head 接到它后面去注意这里的关键——你不需要管后面那一段是怎么反转的你只需要假设它已经反转好了。这个假设就是递归的灵魂。所以判断自己是不是在写递归不看有没有自我调用而看有没有出现更小规模的同类问题这个动作。1.2 不要在脑子里展开全部调用过程这是新手最容易掉进去的坑。人脑的栈大概只能同时装三到四层而一道链表题可能有五千层调用。你硬要在脑子里跑完结果一定是晕。正确做法是只展开三层。拿阶乘来说你在纸上写f(3)、f(2)、f(1)三层的展开确认返回值一层层拼回来是对的就够了。剩下的层数交给计算机它们和你手推的三层遵循完全相同的规则。这就像公司里的层层汇报老板不需要知道每个基层员工怎么干活的他只需要知道我的直接下属会给我一个正确的结果。你写递归的时候就是那个只管一层、信任下一层的角色。1.3 两个类比帮你把直觉建起来类比一俄罗斯套娃。每个娃娃里面装着一个更小的同款娃娃最小的那个是实心的、拆不开的。实心娃娃对应递归里的基准情形一层层的套壳对应递推关系。如果你设计的娃娃永远拆不到实心就会无限拆下去——这就是栈溢出的本质。类比二查一本多卷本的工具书。你要找某个条目先翻到索引索引告诉你这个内容在第三卷。你不需要把前两卷整本读完你只需要拿到第三卷、重复同样的查找动作直到某一卷直接给出答案。每一卷的查找流程完全一样这就是结构相同的子问题。把这两个类比记住后面所有内容都是它们的展开。1.4 递归和数学归纳法是同一套东西如果你学过数学归纳法会发现它和递归是同一件事的两个方向。归纳法证明两步n 1时成立基准情形假设n k成立能推出n k 1也成立递推关系。递归写代码同样是两步最小的输入怎么处理以及已知更小规模的结果怎么算出当前规模的结果。这个联系不是巧合。写递归卡住的时候我自己的习惯是先把这两条用中文写出来比如最小情况链表为空时返回空。递推假设head.next之后的部分已经反转完成我把head挂到反转后链表的末尾。这两句话写完代码基本就直接翻译出来了。如果你连这两句话都写不完整那说明对这个问题的结构还没想清楚此时写代码是在赌运气。2. 递归的三个零件缺一个就出问题2.1 基准情形不是随手写个 return边界要想全基准情形就是让递归停下来的那个条件。新手最常见的错误是只考虑了最常规的最小输入漏掉了各种边角。以二叉树最大深度为例很多人写def maxDepth(root): if root.left is None and root.right is None: return 1 return max(maxDepth(root.left), maxDepth(root.right)) 1问题在哪当root是None的时候第一行直接报错因为None没有left属性。正确写法是先拦住空节点def maxDepth(root): if root is None: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 1这里的0和1是有讲究的空节点贡献 0 层深度非空节点自己算一层所以加 1。写基准情形的时候我一般问自己三个问题空输入怎么算、只有一个元素的输入怎么算、超出范围的输入怎么算。这三个问题回答完基准情形基本就全了。2.2 递推关系先假装子问题已经解决递推关系的写法有个固定套路叫信任跳跃。写的时候不去想子问题内部怎么执行直接调用它、拿结果、组合。反转链表的递归写法是把这个套路体现得最明显的例子def reverseList(head): if head is None or head.next is None: return head new_head reverseList(head.next) # 信任后面那段已经反转好了 head.next.next head # 把 head 接到反转段的末尾 head.next None # 断开原来的正向指针避免成环 return new_head注意第 4 行之后head.next指向的仍然是原来那个后继节点而那个节点现在已经是反转段的最后一个了。所以head.next.next head就是在接尾巴。最后必须把head.next置空否则整条链会形成环遍历的时候死循环——这是这道题最高频的踩坑点。2.3 返回值到底该往上带什么递归函数的返回值设计决定了整个函数的形态。常见的有三种类型返回值适用场景例子纯计算型子问题的结果数学递推、深度、求和阶乘、最大深度结果 状态型子问题结果和新状态需要同时知道结果和改到哪了反转链表、合并链表无返回型什么都不返回靠外部变量收集遍历型问题中序遍历收集节点值、回溯新手很容易在第三种上翻车明明不需要返回值却硬要return一个东西然后把结果弄乱。判断标准很简单——如果这个函数的作用是走一遍就用外部变量收集如果它的作用是算出并交回一个值就用返回值。2.4 一张表看清四种典型写错方式错误写法现象根本原因修正没写基准情形栈溢出 / 内存超限递归无法终止补最小输入的处理递归调用的参数没变小栈溢出传入的还是原来的值检查是否传了head.next、n - 1忘了组合子结果返回值恒为基准值只返回了子问题的结果加上当前层的贡献返回值类型前后不一致报类型错误或逻辑错分支里有的返回 None 有的返回值所有分支统一返回类型把这四种对照着看一遍你会发现递归的 bug 基本都在这张表里。3. 调用栈递归看不见的成本都在这里3.1 每一层调用都占一块内存函数每被调用一次系统就在调用栈上压入一个栈帧里面存着这次调用的参数、局部变量、以及执行完之后该回到哪一行。递归调用 N 层栈上就有 N 个栈帧叠着。这些栈帧是真实占用内存的。不同语言和运行环境的默认栈大小不一样经验值是几千层到一万层左右还算安全十万层基本必爆。所以在 LeetCode 上写链表递归如果题目提示节点数最多几千个递归是能过的如果节点数上限是十万那你得改成迭代或者换个思路。注意递归的深度和你写了几行代码没关系只和最多同时存在几层未返回的调用有关。一个只有三行的递归函数照样可以爆栈。3.2 时间复杂度看节点总数乘以每层工作量递归的时间复杂度分析有个固定套路总工作量 递归树上的节点个数 × 每个节点内部的工作量。阶乘、反转链表每层只做常数时间的操作一共 N 层所以是O(N)。二叉树遍历每个节点被访问一次每次做常数操作所以是O(N)。朴素斐波那契递推式是T(n) T(n-1) T(n-2) O(1)展开之后是指数级O(2^n)。二分查找每层问题规模减半T(n) T(n/2) O(1)得到O(log n)。快速幂同理O(log n)。这里有个容易被忽略的点每层内部如果做了O(N)的工作总复杂度会退化。比如有人写反转链表时每次都从头遍历到尾部去找尾节点那总复杂度就是O(N²)在 LeetCode 上多半超时。3.3 空间复杂度就是递归深度递归本身不额外申请数组但它占栈空间而栈空间的量级正好等于递归的最大深度。所以线性递归阶乘、链表O(N)额外空间。平衡二叉树的递归深度是O(log N)额外空间O(log N)。退化成链的二叉树深度变成O(N)额外空间跟着变成O(N)。这也是为什么面试官经常追问一句你的空间复杂度是多少——他们在看你有没有意识到调用栈的开销。很多人只算了自己 new 出来的几个变量把栈忘了。3.4 尾递归这件事别抱太大期望尾递归指的是递归调用是函数体里最后一个动作且返回值直接就是递归调用的返回值。理论上这种写法可以被编译器优化成循环不占额外栈空间。但现实是主流常用语言里这类优化要么默认不开要么根本不支持。所以不要指望写个尾递归就能规避栈溢出。真遇到深度很大的场景老老实实改成迭代比赌编译器靠谱。4. 简单题里最常见的几类递归模板4.1 线性递归阶乘、累加、斐波那契这是最基础的一类问题规模每层减 1。def factorial(n): if n 1: return 1 return n * factorial(n - 1)public int factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); }基准情形写n 1而不是n 1是一个防御性习惯。万一传进来 0 或者负数也不会无限递归下去。零基础阶段多写一个等号能省掉很多调试时间。斐波那契的朴素版本是反面教材def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个写法在n 30左右就开始明显变慢n 50基本等不到结果。原因是同一批子问题被反复计算了无数次。加一个缓存就解决from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个改造叫记忆化本质是算过一遍就存起来。它是把递归题从超时救回来的第一手段值得单独记住。4.2 链表递归反转与合并反转链表上面已经给过。合并两个有序链表的递归思路同样简洁def mergeTwoLists(l1, l2): if l1 is None: return l2 if l2 is None: return l1 if l1.val l2.val: l1.next mergeTwoLists(l1.next, l2) return l1 else: l2.next mergeTwoLists(l1, l2.next) return l2这道题的基准情形非常直观一条链空了直接把另一条整段接上就行不需要再逐个比较。这里体现的是基准情形可以一次处理掉一批数据不是非得精确到单个元素。写链表递归的时候我强烈建议在草稿纸上画两个节点的小例子把指针的每一次变化画出来。链表题的 bug 基本都是指针改错方向或者形成了环画图比盯着代码看快得多。4.3 二叉树递归深度、对称、路径二叉树是递归最自然的载体因为树本身就是递归定义的。一套通用骨架def solve(node): if node is None: return 空节点的基础值 left solve(node.left) right solve(node.right) return 组合 left、right 和 node 自己把骨架记住剩下的只是填空。最大深度填max(left, right) 1节点求和填left right node.val判断对称需要改成两个指针同时走def isSymmetric(root): if root is None: return True return check(root.left, root.right) def check(a, b): if a is None and b is None: return True if a is None or b is None: return False return a.val b.val and check(a.left, b.right) and check(a.right, b.left)对称判断的关键在于镜像配对左子树的左边要和右子树的右边比。第一次写的人经常把check(a.left, b.left)写进去跑小样例还看不出来换个不对称的树就露馅了。这也是为什么我在 4.1 里强调要拿多个样例验证——递归的错往往很隐蔽。4.4 分治与二分从查找到快速幂分治的核心是把问题一分为二分别解决再合并。二分查找是它最简单的形态def binarySearch(nums, target, lo, hi): if lo hi: return -1 mid lo (hi - lo) // 2 if nums[mid] target: return mid if nums[mid] target: return binarySearch(nums, target, mid 1, hi) return binarySearch(nums, target, lo, mid - 1)mid lo (hi - lo) // 2这个写法是为了避免lo hi溢出虽然 Python 不存在这个问题但换成 Java 或 C 就很重要。这个习惯越早养成越好。快速幂是分治的经典应用x^n不用乘 n 次而是折半def power(x, n): if n 0: return 1.0 half power(x, n // 2) if n % 2 0: return half * half return half * half * x这里half一定要用变量存下来不能写成power(x, n//2) * power(x, n//2)否则一次递归裂变成两次复杂度立刻从O(log n)退化回O(n)。同一个子问题的结果要复用是分治里最容易踩的坑。顺带说一句二分答案类题目比如那类爱吃香蕉的狒狒的题它看着像模拟实际正解是枚举答案空间做二分。它的check函数是普通循环整体不写递归但思想上是分治的兄弟。很多人一看到每小时吃几根就想用递归去穷举所有速度组合那是把简单问题做成了指数级遇到这类题要知道往二分方向转。4.5 递归子程序法把表达式语法分析讲清楚热词里出现了表达式语法分析——递归子程序法这其实是递归在编译方向的经典应用顺手讲一下你会发现它和 LeetCode 上的树递归是一回事。一个只含加减乘除和括号的表达式可以用一套简化文法描述表达式 - 项 { (|-) 项 } 项 - 因子 { (*|/) 因子 } 因子 - 数字 | ( 表达式 )递归子程序法就是每一个非终结符写成一个函数函数之间互相调用遇到递归定义的产生式就直接递归。核心是这样def parse_expr(tokens): value parse_term(tokens) while peek(tokens) in (, -): op next_token(tokens) rhs parse_term(tokens) value value rhs if op else value - rhs return value def parse_term(tokens): value parse_factor(tokens) while peek(tokens) in (*, /): op next_token(tokens) rhs parse_factor(tokens) value value * rhs if op * else value / rhs return value def parse_factor(tokens): token next_token(tokens) if token (: value parse_expr(tokens) # 回到最外层递归闭环 expect(tokens, )) return value return float(token)注意parse_factor遇到左括号时又调回了parse_expr这个闭环就是递归的体现也是它能正确处理任意层嵌套括号的原因。把乘除放在比加减更深的层级就自然实现了优先级。为什么这套方法值得零基础的人看一眼因为它把结构决定代码这件事展示得特别清楚。你写不出解析器往往不是不会写代码而是没把文法结构理清楚。一旦文法写对了函数几乎是照着文法抄下来的——这和前面说的递归题先用中文写出基准情形和递推关系是同一个方法论。5. 递归写挂了按这个顺序查5.1 栈溢出先看基准情形再看参数栈溢出说明递归没有收敛。排查顺序有没有基准情形。有些新手写了一半就把if删了去改后面的逻辑改着改着忘了加回来。基准情形的条件是否真的会被触发。比如if n 0但递归调用传的是n - 2那n从 1 开始就永远到不了 0。递归调用的参数是否确实在向基准情形靠近。链表题最常见的就是传了head而不是head.next自己调自己一秒爆栈。有没有间接自调用形成的死循环。函数 A 调 BB 又调 A两边都没有终止条件这种问题看栈信息能看出来栈帧里会交替出现两个函数名。5.2 结果不对先验证基准情形再打印深度结果错了但没溢出问题通常在组合环节。我一般的做法是加一个depth参数把每层的输入和返回值打印出来def solve(node, depth0): print( * depth enter: str(node)) if node is None: return 0 result max(solve(node.left, depth 1), solve(node.right, depth 1)) 1 print( * depth return: str(result)) return result缩进能让你一眼看出层的结构比盲目看代码快十倍。不过要记得LeetCode 上提交前必须把打印删掉否则会因为输出过多被判错。更快的办法是只测三个用例最小输入、只有一个元素的输入、一个稍微大一点的输入。如果小用例过了大用例挂多半是组合逻辑或者边界遗漏如果最小用例就挂直接去看基准情形。5.3 超时先看有没有重复计算递归超时九成是重复子问题。判断方法很直接数一下递归树上一共有多少个节点如果节点数远大于问题规模那就说明有重复。改造手段就是记忆化用字典或者数组存下已经算过的结果进入函数第一件事是查缓存。LeetCode 上很多题的N只有几十这种情况套记忆化几乎必过。另一个超时原因是每层做了太重的工作。比如在递归里套一层循环遍历整条链表复杂度直接变成平方级。这种情况得想办法把每层的工作量降到常数通常靠传一个额外的状态参数来实现。5.4 递归改迭代的三条路不是所有场合都适合递归。链表长度十万、树退化成链这些情况下递归有爆栈风险。改写路径有三条手动栈模拟。自己维护一个栈把递归的压栈出栈过程显式写出来。灵活但代码量大。改成循环 局部变量。线性的递推阶乘、累加、反转链表都能直接改写成 for 循环这是最省事的。改成自底向上的表。斐波那契这类可以用两个变量滚动推进复杂度从O(N)空间降到O(1)。我自己的取舍是树和链表的遍历优先用递归写代码短、可读性好一旦题目数据规模明显偏大或者明确提示深度可能很深就直接上迭代。5.5 一道题的完整复盘模板练递归做完题之后的复盘比做题本身更重要。我一般按这四项记录复盘项记录内容三个零件基准情形是什么、递推关系怎么描述、返回值代表什么复杂度时间复杂度推导过程、递归深度、额外空间踩坑点这次写挂的地方、为什么挂、以后怎么避免迭代版能不能改成循环、改完之后差别在哪坚持记录二十道题你会发现自己错的地方高度重复基本就是前面那张表里的四种。6. 零基础练递归的节奏安排6.1 按这个梯度推进不要跳递归的难度是台阶式的跳过任何一级都会卡住。阶段题目类型目标第一周阶乘、求和、斐波那契把三个零件的写法变成本能第二周反转链表、合并两个有序链表适应指针操作和边界判断第三周二叉树最大深度、对称二叉树、路径求和掌握通用骨架和双指针递归第四周二分查找、快速幂、幂函数理解分治和log级复杂度巩固期简单题中的递归类目混合刷做到看到题就知道用不用递归每一阶段至少写十道同类题。写递归和学游泳一样看再多教程都不如自己下水扑腾。第一遍写不出来就看题解但看完之后必须合上题解自己重写一遍这一步不能省。6.2 每道题只做三件事我做递归题的习惯流程是先用中文写两句话——最小情况怎么处理、更小规模的结果怎么组合。翻译成代码不追求一次写对先让逻辑跑通。手推三层展开在小样例上验证返回值是不是一层层正确拼起来的。第三件事最容易被跳过但它恰恰是唯一能防止看起来对、实际错的步骤。递归的 bug 有个特点经常能过掉最简单的样例在一个稍复杂的地方才暴露。6.3 几个高频疑问递归是不是很难要不要先背模板模板可以背但只背骨架不够。骨架是if 空节点: return 基础值加一行组合真正会变的是基准值取多少、组合方式是什么。这两个必须靠理解。写递归需要天赋吗不需要需要的是不跳步。新手写不出递归八成是因为想一步写出完整代码而不是先把那两句话想清楚。面试中递归题要注意什么除了写对一定要主动说明递归深度和空间复杂度并且准备好如果数据量很大怎么办的答法。能说出数据规模到十万就改迭代比只会写递归要加分。周赛里的递归题一般什么难度出现在前半段的递归题基本都是树的遍历或链表操作属于模板级别拼的是手速和准确率不是思路后半段如果出现递归通常是树形结构上配合状态传递那已经超出简单递归的范围了等基础扎实了再碰。我个人在这块踩过的坑刚刷题那阵子我最大的问题是能看懂但写不出。后来发现根子在于我总是试图一次性理解整个递归流程而不是老老实实把基准情形和递推关系用中文写下来。养成了先写两句话的习惯之后效率提升非常明显。另一个坑是低估了调用栈的成本。有一次写一道链表题本地跑小数据完全没问题提交之后报内存超限查了半天才发现是递归深度太大。从那之后我养成一个习惯写递归之前先看一眼数据规模的上限超过几万的直接考虑迭代。最后分享一个我觉得最有用的小技巧写完递归之后专门造一个最不常规的输入去测。空链表、单节点、全相同的值、退化成一条链的树——这几个用例能过滤掉绝大多数隐藏 bug。把它们做成自己的固定测试集每道题都跑一遍比反复看代码有效得多。