如果要我在所有编程概念里挑一个“看代码觉得自己懂了、合上屏幕立刻懵了”的东西递归绝对排第一。尤其是刚开始接触基本递归函数那会儿一行return n * factorial(n - 1)翻来覆去看了半天觉得作者的思路简直行云流水可真轮到自己写或者想手动跟一遍执行过程大部分人三分钟就开始怀疑是不是自己智商有问题。我这些年见过不少学编程的朋友在这一步摔跟头后来慢慢总结出一个规律递归卡住的人几乎都卡在同一个地方——把递归理解成了“函数自己调用自己”这个表面现象却没有真正理解递归背后的两样东西调用栈以及“把大问题拆成同构小问题”的思维方式。所以这篇我想抛开花哨的框架用最直白的手工追踪方式把递归的基本原理、五六个经典入门函数、常见的翻车原因和调试方法一次性讲透。写给你也写给当年那个在递归面前卡了整整两天的我自己。1. 递归的核心不是“自己调用自己”而是“拆”和“停”1.1 递归函数的两个部分基线条件与递归条件任何一个能正常结束的递归函数结构上只有两个部分基线条件base case和递归条件recursive case。别被术语吓到基线条件就是“问题已经小到不用再拆了直接给答案”的那个分支递归条件就是“问题还有得拆于是调用一个规模更小的自己”。写的时候只要保证两点递归条件一定让问题规模朝基线方向缩小基线条件必须有一天能被触达。两条都做到了这个递归函数就是自洽的。为什么这是理解递归的第一道门因为绝大多数人写不出递归不是逻辑不行而是在一开始就想一次性把整条调用链看透结果越看越乱。其实递归的写法是一个“只关心当前层”的过程你不用管下一层发生了什么细节你只需要相信传给下一层的输入既然更小那么它一定能按同样的规则返回一个正确结果。这个信念在算法领域有个专门的说法叫“递归信赖”recursive leap of faith。你先假设“下一层一定正确”然后把当前这层拼上去最后你会发现这个假设恰好就是整个函数的正确性证明。1.2 递归信赖向数学归纳法借来的思维方式我记得当初带我入门的某位学长打过一个比方递归函数就像一队人传接力棒你要做的是把自己的这一棒规范地交到后面的人手里你只需要保证“我这一棒没问题”至于后面那个人怎么跑完他自己的路程你不用操心也别去操心。这个思路和数学归纳法完全同构先证明 n0 时命题成立对应基线条件再证明“若 nk 时成立则 nk1 时也成立”对应递归条件于是所有自然数就都成立了。递归函数完美复刻了这个结构基线条件处理最小问题递归条件把当前问题和“更小的问题”联系起来。一旦你真接受了这个思维方式写递归就变成了一件很机械的事情——判断当下这一层要不要继续拆、该往哪个方向拆然后放心地把剩下的交给下一层。很多人学递归的瓶颈不在语法而在心态总想一眼看穿所有层越看越慌最后干脆放弃了背答案。我自己的经验是带着“先信后证”的心态去抄、去写、去改几个经典例子比原地硬想两个小时效率高得多。1.3 为什么“自己调用自己”这个说法坑了无数新手“函数调用自己”这句话本身没错但它很容易被理解成“函数在运行中突然变成另一个函数无限地复制自己”于是很多新手脑补出一幅“自己生自己、无穷无尽”的可怕画面继而彻底卡壳。其实递归调用就是一次普通的函数调用只不过被调用的函数名字和当前函数相同而已。CPU 眼里根本没有“递归”这回事它只看到一条条指令压栈、跳转、返回值、出栈。你调用factorial(5)和调用任何一个普通函数底层动作一模一样。所以千万不要把递归理解成什么神秘魔法。它只是“函数调用自身”这个普通动作加上“拆解与停止”这两条逻辑约束之后自然呈现出来的结果。想通了这一层再看网上那些“递归就是调用自己”的解释你就知道他们只描述了一个外壳真正重要的内胆是往哪个方向拆以及什么时候停。2. 基本递归函数入门五连从阶乘到回文判断逐个手写给你看2.1 阶乘递归的“Hello World”先上最经典的入门函数——阶乘def factorial(n): if n 1: return 1 return n * factorial(n - 1)别看它只有五行它把递归函数的全部要素都装齐了。if n 1: return 1是基线条件处理最小输入return n * factorial(n - 1)是递归条件把问题从 n 缩小到 n-1并且在“当前层”做乘法。写递归的第一习惯就是先把出口写好再写递归调用这样结构上就不会漏掉基线条件也更容易读。我见过太多人第一次写阶乘时写出这种版本def factorial(n): return n * factorial(n - 1)然后一脸无辜地问为什么程序卡死了。这就是前面说的情况没有出口或者说基线条件压根没写。所以每当你准备写一个基本递归函数先在纸上回答一个问题输入小到什么程度时这个问题可以直接给出答案答案就是你的基线条件。2.2 数组求和、幂运算与回文判断同一个骨架的三种变体阶乘只是热身基本递归函数的真正威力在于处理数据。来看三个同样骨架的例子。第一个是数组求和def sum_list(nums): if not nums: return 0 return nums[0] sum_list(nums[1:])基线条件是“数组为空和为 0”递归条件是“第一个元素 剩下所有元素的和”。对比阶乘你会发现结构几乎一模一样处理当前一小块递归处理剩余一大块。第二个是幂运算def power(x, n): if n 0: return 0 if x 0 else 1 return x * power(x, n - 1)基线条件是n 0时返回 1这里额外处理了 0 的 0 次方这种边界按你的业务约定来就行递归条件是x * x^(n-1)。第三个是经典的判断回文def is_palindrome(s): if len(s) 1: return True if s[0] ! s[-1]: return False return is_palindrome(s[1:-1])回文判断有两个基线条件长度小于等于 1 说明中间只剩一个字符或没有字符必然是回文首尾字符不相同直接判定不是回文。递归条件则是把字符串从两端各砍掉一个字符继续判断中间部分。这三个例子合起来能帮你形成一个肌肉记忆基本递归函数的骨架永远是从“最小输入”和“当前层操作 更小输入”这两端出发去凑出来的。2.3 写一个递归函数的四个固定步骤看了上面几个例子你可能已经摸到规律了。我把它整理成可以直接套用的四步流程判断什么样的输入是“小到不能再拆”的写出基线条件的返回值。确定当前层要做的一个操作并找出比当前输入小一号的输入长什么样。假设递归调用能返回正确结果把它代入当前层的操作拼出完整的递归式子。检查第 3 步的“缩小操作”是否一定会抵达第 1 步的基线条件如果永远到不了说明递归条件设计有 bug。比如阶乘最小输入是 0 或 1返回 1当前层操作是乘法小一号输入是 n-1代入得到n * factorial(n - 1)n 一直减 1必然到达基线。四步走完一个基本递归函数就出来了。这个方法对树、链表、字符串等结构同样适用只是“小一号输入”变成了“子树”“下一个节点”“去掉首尾的子串”而已。3. 递归执行链路拆解用手工追踪看清每一层栈帧发生了什么3.1 factorial(5) 的“递”与“归”一条表达式链代码写出来简单不代表执行过程简单。当你调用factorial(5)时机器实际展开的是一长串嵌套表达式factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2))) 5 * (4 * (3 * (2 * factorial(1)))) 5 * (4 * (3 * (2 * 1))) 120这个过程分为两半前半段“递”不断把问题拆小、往深处调用后半段“归”从最底层拿到结果后一层层往回算乘法。这也是“递归”这两个字的由来——先递进再回归合起来才是一个完整的递归过程。3.2 用一张表看清调用栈每一层到底在等什么光看表达式链还不够直观我建议你把每一层调用当作一张“待办清单”来看。下面这张表是factorial(5)的调用栈快照调用层次当前调用这一层在等待什么归的过程中返回什么1factorial(5)等 factorial(4) 的结果然后乘 51202factorial(4)等 factorial(3) 的结果然后乘 4243factorial(3)等 factorial(2) 的结果然后乘 364factorial(2)等 factorial(1) 的结果然后乘 225factorial(1)基线条件不再递归1注意观察表中的前四层都在“等待”每一层的栈帧都把局部变量 n 和要做的乘法挂在内存里直到第五层命中基线条件后结果才开始从下往上传递。这就是为什么递归的空间复杂度是 O(n)——它需要为每一层调用都保留一个栈帧直到最底层返回才逐一释放。3.3 斐波那契的调用树它不是一条链而是一棵树阶乘的调用链是线性的好追踪但斐波那契就不一样了。它的递归写法同样非常简洁def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)可执行过程长这样以 fib(5) 为例fib(5) -- fib(4) -- fib(3) | -- fib(2) | -- fib(1) -- fib(2) -- fib(1) -- fib(0) -- fib(3) -- fib(2) -- fib(1)你看到问题了吗fib(3)被重复计算了两次fib(2)被重复计算了三次。层次越深重复的节点越爆炸。到这里就能引出一条理解递归的关键结论时间开销要看整棵调用树的节点总数空间开销只看从根到叶子的最大路径深度。也就是说fib(n)这种朴素递归虽然每一层的栈帧深度只有 O(n)但总调用次数是指数级的。这也是为什么我总说不是所有能递归写出来的程序都适合递归代码简洁和执行高效是两码事。4. 递归的三个“翻车现场”无限递归、重复计算与栈溢出4.1 漏写基线条件一次 RecursionError 现场还原有一回帮一位朋友查代码他写了一个“带日志的阶乘”结果把出口写在递归调用之后原意是打印每次的参数结果函数长这样def bad_factorial(n): return n * bad_factorial(n - 1)调用bad_factorial(5)之后程序一路调用bad_factorial(4)、bad_factorial(3)……永远碰不到出口直到 Python 抛出RecursionError: maximum recursion depth exceeded。我当时的排查过程很简单先看有没有循环没有再打印调用参数发现 n 一路减到负数还在跑最后才意识到是递归没有出口。整个过程没什么高深技巧但它代表了递归最常见的 bug——基线条件缺失或不可达。所以我再强调一次写递归函数第一件事不是写递归调用而是先写出口。提示写基本递归函数时我的习惯是先写if ...: return ...的基线分支再写递归分支。这样只要瞄一眼函数结构就知道出口在不在。4.2 重复计算fib(40) 为什么慢到让人怀疑人生斐波那契是重复计算的“头号教材”。我们用递推式来算一下调用次数设 T(n) 为计算fib(n)所产生的总调用次数则 T(0)1、T(1)1且对 n2 有 T(n)T(n-1)T(n-2)1。算下来fib(40)的调用次数超过 3 亿次在我电脑上要跑好几秒fib(50)更是到了几百亿次基本属于“你等它它也在等你”的状态。原因就是调用树里同一个子问题被反复求解完全没有复用。解决办法我在后面第 6 节会详细说核心思路是“记忆化”——把已经算过的结果存起来下次直接查表。这里先记住一条判断标准如果你发现某个递归函数的调用树里有大量重复节点那它就有重复计算问题要么加缓存要么改写成循环。4.3 栈溢出与深度限制Python 默认 1000 层背后的原理每一次递归调用都会在内存里压入一个栈帧栈帧里保存着参数、局部变量、返回地址等信息。程序可用的栈空间是有限的压得太深就会栈溢出。Python 为了不让解释器把自己压垮默认把递归深度限制在 1000 层左右超出就抛RecursionError。而 C/C 这类语言不设这种软限制深度超了直接段错误崩溃连报错都比 Python 硬核得多。有人遇到RecursionError会直接调sys.setrecursionlimit(10000)硬提上限我这里要泼一盆冷水这个操作有风险Python 的每层调用本身还占用 C 栈你把软限制调得过高最终可能导致解释器直接崩溃。所以在实际项目里能用循环解决的线性问题很少真的用深递归一旦数据规模可能超过几百层就要提前警惕栈溢出而不是等它爆了再去救火。5. 递归与循环怎么选三个判断标准加一张对比表5.1 判断标准一问题本身是否具有“递归结构”递归最舒服的场景是问题本身就长着一副“由更小的自己组成”的样子。典型的例子是二叉树遍历def traverse(node): if node is None: return visit(node) traverse(node.left) traverse(node.right)这段代码用循环写就很别扭——你得自己维护一个栈手动压入左右子树还得小心处理遍历顺序用递归写几乎是把树的定义原封不动翻译成代码。类似的场景还有 JSON/XML 嵌套解析、文件目录遍历、表达式求值、深拷贝它们的共同特征都是“每层结构相同、但嵌套深度事先不确定”。这种情况下递归不只是图省事而是可读性最好的表达方式。5.2 判断标准二递归深度与数据规模是否可控即便问题结构上适合递归也要看深度能不能兜住。如果数据规模可能无限增长比如一个大到变态的链表、一个超长的字符串递归深度就会跟着数据量线性上升随时可能触到栈顶。反过来像二叉树这类结构树高通常只有几十到几百层递归深度是有天然上限的用起来就很安全。我的实用判断是如果你能拍着胸脯说“这个递归最多也就几百层”那就放心用如果数据量不受控比如用户可能上传一个几千层的嵌套结构那就要考虑迭代或显式栈。这里的核心原则是递归的栈帧深度直接等同于运行时风险别拿测试用例的规模去猜测线上数据的脾气。5.3 一张表看清递归与迭代的代价差异对比维度递归迭代代码可读性结构同构时极高线性逻辑时也清晰时间开销有函数调用、压栈弹栈开销无额外调用开销空间开销每层一个栈帧深度 O(n)通常 O(1)栈溢出风险有深度不可控时风险大基本无天然适用场景树、嵌套数据、分治数组求和、循环计数、线性扫描注意这张表讨论的是“朴素递归”。加上记忆化、尾递归等手段后递归在时间和空间上的很多劣势是可以缓解的但它仍然摆脱不了“每一层都需要单独栈帧”这个基本事实。所以我的决策习惯往往是优先看结构结构上像树、像嵌套那就递归结构上就是一条直线那就循环不要为了炫技硬递归。6. 调试与优化递归的实用工具箱print追踪、边界测试、记忆化与尾递归6.1 缩进 print 法让每一层调用和返回都变成可视日志调试递归最土也最有效的办法是在函数入口和出口各打一条日志并用一个 depth 参数控制缩进。我给factorial加几行日志def factorial(n, depth0): print( * depth f进入 factorial({n})) if n 1: print( * depth 命中基线返回 1) return 1 result n * factorial(n - 1, depth 1) print( * depth ffactorial({n}) 拿到子结果返回 {result}) return result跑一次factorial(4)输出会像一张展开的地图进入 factorial(4) 进入 factorial(3) 进入 factorial(2) 进入 factorial(1) 命中基线返回 1 factorial(2) 拿到子结果返回 2 factorial(3) 拿到子结果返回 6 factorial(4) 拿到子结果返回 24排查的时候我还会在日志里额外打印当前参数的关键属性比如字符串还剩多长、数组还剩几个元素以此确认“每一步都在朝基线条件前进”。能确认这一点递归的一大半 bug 就已经被你肉眼揪出来了。6.2 边界值先行先测最小的输入写递归函数时先测最小输入几乎是一条铁律。n0、n1、空数组、单元素字符串这些输入要么直接命中基线条件要么只触发一层递归执行路径最简单最适合验证“基线条件写对了”。然后再测稍微正常的输入比如 n5、n10观察结果是否符合预期。很多同学一上来就测大数程序崩了之后分不清是逻辑错还是栈溢出排查成本直接翻倍。我自己的顺序永远是边界值 → 小规模验证 → 真实规模。6.3 记忆化用一张缓存表消灭重复计算针对第 4 节说的重复计算问题最直接的药方是记忆化。给斐波那契函数加个缓存每个子问题只算一次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]这里有一个值得注意的细节memo的默认值要写成None而不是直接写成{}。因为可变默认参数会在多次调用之间共享同一个字典虽然在这个场景里凑巧能用但很容易埋下隐患写成if memo is None: memo {}才是干净可靠的做法。加了缓存之后fib_memo(100)也能瞬间算完因为后面的所有调用都是 O(1) 查表。这个思路放在任何“递归树有重复节点”的问题上都成立是一条通用的优化路径。6.4 尾递归与显式栈两种进阶优化方式尾递归指递归调用发生在函数体的最后一步并且没有任何计算需要等它返回后再完成def factorial_tail(n, acc1): if n 1: return acc return factorial_tail(n - 1, acc * n)在支持尾调用优化的语言比如不少函数式语言里编译器可以把尾递归改写成循环从而不消耗额外栈帧。但 Python 官方解释器没有做这个优化你就算写成尾递归照样压栈、照样可能RecursionError。所以在 Python 里我把尾递归当成一种“理解递归如何转成迭代”的思维练习而不是实际的性能优化手段。真正的性能优化除了缓存还有显式栈。比如二叉树遍历的递归版本本质上是在借助系统调用栈你完全可以自己用一个列表来模拟栈def traverse_iter(root): stack [root] while stack: node stack.pop() if node is None: continue visit(node) stack.append(node.right) stack.append(node.left)这个版本不产生新的函数调用深度再大也不怕栈溢出。它展示了一条很好的思维路径递归背后的调用栈本来就是一种你可以自己接管的数据结构。理解了这一点你对递归的理解就再也不是“背模板”而是真正看穿了它的底牌。最后多聊一句我的个人感受。这些年我教过不少人写基本递归函数发现大家从“看得懂”到“写得对”之间差的就是那几次主动的手工追踪。你不需要把递归想象成什么高深莫测的东西它就是“拆解 停止 同构子问题”这三件事的组合。真遇到搞不懂的时候拿出纸笔画一棵调用树或者像我上面那样在代码里塞几个 print比盯着屏幕硬想高效得多。如果你现在正卡在递归这道门槛上我的建议是别贪多找三五个最基础的函数——阶乘、求和、回文判断、斐波那契、二叉树遍历——每个都手工追踪两遍把整个过程跑熟。等你能闭着眼画出factorial(4)的调用栈那一刻你放心递归对你来说就再也不是什么门槛了。 
长河君 · 2026/10/24 5:52:40 · 阅读 1.2k 递归原理与调用栈：从阶乘到斐波那契的入门指南
如果要我在所有编程概念里挑一个“看代码觉得自己懂了、合上屏幕立刻懵了”的东西递归绝对排第一。尤其是刚开始接触基本递归函数那会儿一行return n * factorial(n - 1)翻来覆去看了半天觉得作者的思路简直行云流水可真轮到自己写或者想手动跟一遍执行过程大部分人三分钟就开始怀疑是不是自己智商有问题。我这些年见过不少学编程的朋友在这一步摔跟头后来慢慢总结出一个规律递归卡住的人几乎都卡在同一个地方——把递归理解成了“函数自己调用自己”这个表面现象却没有真正理解递归背后的两样东西调用栈以及“把大问题拆成同构小问题”的思维方式。所以这篇我想抛开花哨的框架用最直白的手工追踪方式把递归的基本原理、五六个经典入门函数、常见的翻车原因和调试方法一次性讲透。写给你也写给当年那个在递归面前卡了整整两天的我自己。1. 递归的核心不是“自己调用自己”而是“拆”和“停”1.1 递归函数的两个部分基线条件与递归条件任何一个能正常结束的递归函数结构上只有两个部分基线条件base case和递归条件recursive case。别被术语吓到基线条件就是“问题已经小到不用再拆了直接给答案”的那个分支递归条件就是“问题还有得拆于是调用一个规模更小的自己”。写的时候只要保证两点递归条件一定让问题规模朝基线方向缩小基线条件必须有一天能被触达。两条都做到了这个递归函数就是自洽的。为什么这是理解递归的第一道门因为绝大多数人写不出递归不是逻辑不行而是在一开始就想一次性把整条调用链看透结果越看越乱。其实递归的写法是一个“只关心当前层”的过程你不用管下一层发生了什么细节你只需要相信传给下一层的输入既然更小那么它一定能按同样的规则返回一个正确结果。这个信念在算法领域有个专门的说法叫“递归信赖”recursive leap of faith。你先假设“下一层一定正确”然后把当前这层拼上去最后你会发现这个假设恰好就是整个函数的正确性证明。1.2 递归信赖向数学归纳法借来的思维方式我记得当初带我入门的某位学长打过一个比方递归函数就像一队人传接力棒你要做的是把自己的这一棒规范地交到后面的人手里你只需要保证“我这一棒没问题”至于后面那个人怎么跑完他自己的路程你不用操心也别去操心。这个思路和数学归纳法完全同构先证明 n0 时命题成立对应基线条件再证明“若 nk 时成立则 nk1 时也成立”对应递归条件于是所有自然数就都成立了。递归函数完美复刻了这个结构基线条件处理最小问题递归条件把当前问题和“更小的问题”联系起来。一旦你真接受了这个思维方式写递归就变成了一件很机械的事情——判断当下这一层要不要继续拆、该往哪个方向拆然后放心地把剩下的交给下一层。很多人学递归的瓶颈不在语法而在心态总想一眼看穿所有层越看越慌最后干脆放弃了背答案。我自己的经验是带着“先信后证”的心态去抄、去写、去改几个经典例子比原地硬想两个小时效率高得多。1.3 为什么“自己调用自己”这个说法坑了无数新手“函数调用自己”这句话本身没错但它很容易被理解成“函数在运行中突然变成另一个函数无限地复制自己”于是很多新手脑补出一幅“自己生自己、无穷无尽”的可怕画面继而彻底卡壳。其实递归调用就是一次普通的函数调用只不过被调用的函数名字和当前函数相同而已。CPU 眼里根本没有“递归”这回事它只看到一条条指令压栈、跳转、返回值、出栈。你调用factorial(5)和调用任何一个普通函数底层动作一模一样。所以千万不要把递归理解成什么神秘魔法。它只是“函数调用自身”这个普通动作加上“拆解与停止”这两条逻辑约束之后自然呈现出来的结果。想通了这一层再看网上那些“递归就是调用自己”的解释你就知道他们只描述了一个外壳真正重要的内胆是往哪个方向拆以及什么时候停。2. 基本递归函数入门五连从阶乘到回文判断逐个手写给你看2.1 阶乘递归的“Hello World”先上最经典的入门函数——阶乘def factorial(n): if n 1: return 1 return n * factorial(n - 1)别看它只有五行它把递归函数的全部要素都装齐了。if n 1: return 1是基线条件处理最小输入return n * factorial(n - 1)是递归条件把问题从 n 缩小到 n-1并且在“当前层”做乘法。写递归的第一习惯就是先把出口写好再写递归调用这样结构上就不会漏掉基线条件也更容易读。我见过太多人第一次写阶乘时写出这种版本def factorial(n): return n * factorial(n - 1)然后一脸无辜地问为什么程序卡死了。这就是前面说的情况没有出口或者说基线条件压根没写。所以每当你准备写一个基本递归函数先在纸上回答一个问题输入小到什么程度时这个问题可以直接给出答案答案就是你的基线条件。2.2 数组求和、幂运算与回文判断同一个骨架的三种变体阶乘只是热身基本递归函数的真正威力在于处理数据。来看三个同样骨架的例子。第一个是数组求和def sum_list(nums): if not nums: return 0 return nums[0] sum_list(nums[1:])基线条件是“数组为空和为 0”递归条件是“第一个元素 剩下所有元素的和”。对比阶乘你会发现结构几乎一模一样处理当前一小块递归处理剩余一大块。第二个是幂运算def power(x, n): if n 0: return 0 if x 0 else 1 return x * power(x, n - 1)基线条件是n 0时返回 1这里额外处理了 0 的 0 次方这种边界按你的业务约定来就行递归条件是x * x^(n-1)。第三个是经典的判断回文def is_palindrome(s): if len(s) 1: return True if s[0] ! s[-1]: return False return is_palindrome(s[1:-1])回文判断有两个基线条件长度小于等于 1 说明中间只剩一个字符或没有字符必然是回文首尾字符不相同直接判定不是回文。递归条件则是把字符串从两端各砍掉一个字符继续判断中间部分。这三个例子合起来能帮你形成一个肌肉记忆基本递归函数的骨架永远是从“最小输入”和“当前层操作 更小输入”这两端出发去凑出来的。2.3 写一个递归函数的四个固定步骤看了上面几个例子你可能已经摸到规律了。我把它整理成可以直接套用的四步流程判断什么样的输入是“小到不能再拆”的写出基线条件的返回值。确定当前层要做的一个操作并找出比当前输入小一号的输入长什么样。假设递归调用能返回正确结果把它代入当前层的操作拼出完整的递归式子。检查第 3 步的“缩小操作”是否一定会抵达第 1 步的基线条件如果永远到不了说明递归条件设计有 bug。比如阶乘最小输入是 0 或 1返回 1当前层操作是乘法小一号输入是 n-1代入得到n * factorial(n - 1)n 一直减 1必然到达基线。四步走完一个基本递归函数就出来了。这个方法对树、链表、字符串等结构同样适用只是“小一号输入”变成了“子树”“下一个节点”“去掉首尾的子串”而已。3. 递归执行链路拆解用手工追踪看清每一层栈帧发生了什么3.1 factorial(5) 的“递”与“归”一条表达式链代码写出来简单不代表执行过程简单。当你调用factorial(5)时机器实际展开的是一长串嵌套表达式factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2))) 5 * (4 * (3 * (2 * factorial(1)))) 5 * (4 * (3 * (2 * 1))) 120这个过程分为两半前半段“递”不断把问题拆小、往深处调用后半段“归”从最底层拿到结果后一层层往回算乘法。这也是“递归”这两个字的由来——先递进再回归合起来才是一个完整的递归过程。3.2 用一张表看清调用栈每一层到底在等什么光看表达式链还不够直观我建议你把每一层调用当作一张“待办清单”来看。下面这张表是factorial(5)的调用栈快照调用层次当前调用这一层在等待什么归的过程中返回什么1factorial(5)等 factorial(4) 的结果然后乘 51202factorial(4)等 factorial(3) 的结果然后乘 4243factorial(3)等 factorial(2) 的结果然后乘 364factorial(2)等 factorial(1) 的结果然后乘 225factorial(1)基线条件不再递归1注意观察表中的前四层都在“等待”每一层的栈帧都把局部变量 n 和要做的乘法挂在内存里直到第五层命中基线条件后结果才开始从下往上传递。这就是为什么递归的空间复杂度是 O(n)——它需要为每一层调用都保留一个栈帧直到最底层返回才逐一释放。3.3 斐波那契的调用树它不是一条链而是一棵树阶乘的调用链是线性的好追踪但斐波那契就不一样了。它的递归写法同样非常简洁def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)可执行过程长这样以 fib(5) 为例fib(5) -- fib(4) -- fib(3) | -- fib(2) | -- fib(1) -- fib(2) -- fib(1) -- fib(0) -- fib(3) -- fib(2) -- fib(1)你看到问题了吗fib(3)被重复计算了两次fib(2)被重复计算了三次。层次越深重复的节点越爆炸。到这里就能引出一条理解递归的关键结论时间开销要看整棵调用树的节点总数空间开销只看从根到叶子的最大路径深度。也就是说fib(n)这种朴素递归虽然每一层的栈帧深度只有 O(n)但总调用次数是指数级的。这也是为什么我总说不是所有能递归写出来的程序都适合递归代码简洁和执行高效是两码事。4. 递归的三个“翻车现场”无限递归、重复计算与栈溢出4.1 漏写基线条件一次 RecursionError 现场还原有一回帮一位朋友查代码他写了一个“带日志的阶乘”结果把出口写在递归调用之后原意是打印每次的参数结果函数长这样def bad_factorial(n): return n * bad_factorial(n - 1)调用bad_factorial(5)之后程序一路调用bad_factorial(4)、bad_factorial(3)……永远碰不到出口直到 Python 抛出RecursionError: maximum recursion depth exceeded。我当时的排查过程很简单先看有没有循环没有再打印调用参数发现 n 一路减到负数还在跑最后才意识到是递归没有出口。整个过程没什么高深技巧但它代表了递归最常见的 bug——基线条件缺失或不可达。所以我再强调一次写递归函数第一件事不是写递归调用而是先写出口。提示写基本递归函数时我的习惯是先写if ...: return ...的基线分支再写递归分支。这样只要瞄一眼函数结构就知道出口在不在。4.2 重复计算fib(40) 为什么慢到让人怀疑人生斐波那契是重复计算的“头号教材”。我们用递推式来算一下调用次数设 T(n) 为计算fib(n)所产生的总调用次数则 T(0)1、T(1)1且对 n2 有 T(n)T(n-1)T(n-2)1。算下来fib(40)的调用次数超过 3 亿次在我电脑上要跑好几秒fib(50)更是到了几百亿次基本属于“你等它它也在等你”的状态。原因就是调用树里同一个子问题被反复求解完全没有复用。解决办法我在后面第 6 节会详细说核心思路是“记忆化”——把已经算过的结果存起来下次直接查表。这里先记住一条判断标准如果你发现某个递归函数的调用树里有大量重复节点那它就有重复计算问题要么加缓存要么改写成循环。4.3 栈溢出与深度限制Python 默认 1000 层背后的原理每一次递归调用都会在内存里压入一个栈帧栈帧里保存着参数、局部变量、返回地址等信息。程序可用的栈空间是有限的压得太深就会栈溢出。Python 为了不让解释器把自己压垮默认把递归深度限制在 1000 层左右超出就抛RecursionError。而 C/C 这类语言不设这种软限制深度超了直接段错误崩溃连报错都比 Python 硬核得多。有人遇到RecursionError会直接调sys.setrecursionlimit(10000)硬提上限我这里要泼一盆冷水这个操作有风险Python 的每层调用本身还占用 C 栈你把软限制调得过高最终可能导致解释器直接崩溃。所以在实际项目里能用循环解决的线性问题很少真的用深递归一旦数据规模可能超过几百层就要提前警惕栈溢出而不是等它爆了再去救火。5. 递归与循环怎么选三个判断标准加一张对比表5.1 判断标准一问题本身是否具有“递归结构”递归最舒服的场景是问题本身就长着一副“由更小的自己组成”的样子。典型的例子是二叉树遍历def traverse(node): if node is None: return visit(node) traverse(node.left) traverse(node.right)这段代码用循环写就很别扭——你得自己维护一个栈手动压入左右子树还得小心处理遍历顺序用递归写几乎是把树的定义原封不动翻译成代码。类似的场景还有 JSON/XML 嵌套解析、文件目录遍历、表达式求值、深拷贝它们的共同特征都是“每层结构相同、但嵌套深度事先不确定”。这种情况下递归不只是图省事而是可读性最好的表达方式。5.2 判断标准二递归深度与数据规模是否可控即便问题结构上适合递归也要看深度能不能兜住。如果数据规模可能无限增长比如一个大到变态的链表、一个超长的字符串递归深度就会跟着数据量线性上升随时可能触到栈顶。反过来像二叉树这类结构树高通常只有几十到几百层递归深度是有天然上限的用起来就很安全。我的实用判断是如果你能拍着胸脯说“这个递归最多也就几百层”那就放心用如果数据量不受控比如用户可能上传一个几千层的嵌套结构那就要考虑迭代或显式栈。这里的核心原则是递归的栈帧深度直接等同于运行时风险别拿测试用例的规模去猜测线上数据的脾气。5.3 一张表看清递归与迭代的代价差异对比维度递归迭代代码可读性结构同构时极高线性逻辑时也清晰时间开销有函数调用、压栈弹栈开销无额外调用开销空间开销每层一个栈帧深度 O(n)通常 O(1)栈溢出风险有深度不可控时风险大基本无天然适用场景树、嵌套数据、分治数组求和、循环计数、线性扫描注意这张表讨论的是“朴素递归”。加上记忆化、尾递归等手段后递归在时间和空间上的很多劣势是可以缓解的但它仍然摆脱不了“每一层都需要单独栈帧”这个基本事实。所以我的决策习惯往往是优先看结构结构上像树、像嵌套那就递归结构上就是一条直线那就循环不要为了炫技硬递归。6. 调试与优化递归的实用工具箱print追踪、边界测试、记忆化与尾递归6.1 缩进 print 法让每一层调用和返回都变成可视日志调试递归最土也最有效的办法是在函数入口和出口各打一条日志并用一个 depth 参数控制缩进。我给factorial加几行日志def factorial(n, depth0): print( * depth f进入 factorial({n})) if n 1: print( * depth 命中基线返回 1) return 1 result n * factorial(n - 1, depth 1) print( * depth ffactorial({n}) 拿到子结果返回 {result}) return result跑一次factorial(4)输出会像一张展开的地图进入 factorial(4) 进入 factorial(3) 进入 factorial(2) 进入 factorial(1) 命中基线返回 1 factorial(2) 拿到子结果返回 2 factorial(3) 拿到子结果返回 6 factorial(4) 拿到子结果返回 24排查的时候我还会在日志里额外打印当前参数的关键属性比如字符串还剩多长、数组还剩几个元素以此确认“每一步都在朝基线条件前进”。能确认这一点递归的一大半 bug 就已经被你肉眼揪出来了。6.2 边界值先行先测最小的输入写递归函数时先测最小输入几乎是一条铁律。n0、n1、空数组、单元素字符串这些输入要么直接命中基线条件要么只触发一层递归执行路径最简单最适合验证“基线条件写对了”。然后再测稍微正常的输入比如 n5、n10观察结果是否符合预期。很多同学一上来就测大数程序崩了之后分不清是逻辑错还是栈溢出排查成本直接翻倍。我自己的顺序永远是边界值 → 小规模验证 → 真实规模。6.3 记忆化用一张缓存表消灭重复计算针对第 4 节说的重复计算问题最直接的药方是记忆化。给斐波那契函数加个缓存每个子问题只算一次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]这里有一个值得注意的细节memo的默认值要写成None而不是直接写成{}。因为可变默认参数会在多次调用之间共享同一个字典虽然在这个场景里凑巧能用但很容易埋下隐患写成if memo is None: memo {}才是干净可靠的做法。加了缓存之后fib_memo(100)也能瞬间算完因为后面的所有调用都是 O(1) 查表。这个思路放在任何“递归树有重复节点”的问题上都成立是一条通用的优化路径。6.4 尾递归与显式栈两种进阶优化方式尾递归指递归调用发生在函数体的最后一步并且没有任何计算需要等它返回后再完成def factorial_tail(n, acc1): if n 1: return acc return factorial_tail(n - 1, acc * n)在支持尾调用优化的语言比如不少函数式语言里编译器可以把尾递归改写成循环从而不消耗额外栈帧。但 Python 官方解释器没有做这个优化你就算写成尾递归照样压栈、照样可能RecursionError。所以在 Python 里我把尾递归当成一种“理解递归如何转成迭代”的思维练习而不是实际的性能优化手段。真正的性能优化除了缓存还有显式栈。比如二叉树遍历的递归版本本质上是在借助系统调用栈你完全可以自己用一个列表来模拟栈def traverse_iter(root): stack [root] while stack: node stack.pop() if node is None: continue visit(node) stack.append(node.right) stack.append(node.left)这个版本不产生新的函数调用深度再大也不怕栈溢出。它展示了一条很好的思维路径递归背后的调用栈本来就是一种你可以自己接管的数据结构。理解了这一点你对递归的理解就再也不是“背模板”而是真正看穿了它的底牌。最后多聊一句我的个人感受。这些年我教过不少人写基本递归函数发现大家从“看得懂”到“写得对”之间差的就是那几次主动的手工追踪。你不需要把递归想象成什么高深莫测的东西它就是“拆解 停止 同构子问题”这三件事的组合。真遇到搞不懂的时候拿出纸笔画一棵调用树或者像我上面那样在代码里塞几个 print比盯着屏幕硬想高效得多。如果你现在正卡在递归这道门槛上我的建议是别贪多找三五个最基础的函数——阶乘、求和、回文判断、斐波那契、二叉树遍历——每个都手工追踪两遍把整个过程跑熟。等你能闭着眼画出factorial(4)的调用栈那一刻你放心递归对你来说就再也不是什么门槛了。