递归这个话题几乎所有学编程的人都会碰到。阶乘和斐波那契这两个经典例子更是每个教程里都少不了的“入门标配”。但说实话很多人学完这两个例子依然说不清楚递归到底是怎么一步步执行的更别提在真实项目里怎么用了。我当年也是从这两个例子开始踩过无数坑才慢慢摸清了递归的脾性。这篇文章不打算讲教科书里那些干巴巴的定义而是把我从阶乘到斐波那契、再到非递归改造这条路上踩过的坑、想明白的道理一次性捋清楚。适合刚学完函数、想深入理解递归的初学者也适合那些“会写递归但总担心爆栈”的进阶开发者。1. 递归到底是什么先从生活里找感觉1.1 递归不是玄学是“自己调用自己”递归这个词英文叫recursion翻译过来就是“递归、循环、递推”。我在给别人讲的时候习惯用一句大白话解释一个函数在执行过程中直接或间接地调用了它自己。直接调用很好理解比如函数f里面又调用了f间接调用则是f调了gg又调了f绕了一圈还是回到自己。生活里其实到处都是递归的影子。俄罗斯套娃是一个打开一个娃娃里面还有一个小一号的娃娃再打开还有更小的直到最后那个无法再打开的实心娃娃。你每打开一层做的事和上一层完全一样只是“规模”变小了。还有两面镜子对着放你站在中间会看到无限个自己延展开去。这些都是递归的直觉模型。编程里的递归也是如此把一个复杂的大问题拆解成一个稍微简单一点的同类型问题一直拆到某个不能再拆的“最小单元”然后把结果一层层返回回去。这里有个经典笑话字典里查“递归”这个词给出的解释是“递归参见递归”。好笑归好笑其实挺传神的——递归本身就是用自己来定义自己。1.2 递归的两个核心要素基线条件与递归步骤光知道“自己调用自己”还不够写递归必须抓住两个关键条件。少了任何一个程序都会跑飞。第一个叫基线条件Base Case也常叫终止条件或递归出口。它就是那个“最小的、不需要再调用自己的情况”。比如套娃最里面那个实心的娃娃一打开发现没有更小的了这就到头了直接返回。没有基线条件的递归就像没有出口的迷宫会一直调用下去直到程序崩溃。第二个叫递归步骤Recursive Case也就是“如何把问题规模缩小”的规则。每一次递归调用都必须让问题变得更小一点一步一步逼近基线条件。如果递归调用没有让问题规模变化比如f(n)里面又去调f(n)那它永远也到不了基线条件一样是死循环。我经常拿“爬楼梯”来做类比想爬到第10级台阶我可以先爬到第9级然后迈一步想爬到第9级可以先爬到第8级再迈一步……一直退到“站在第0级台阶上”这个不需要再爬的基本事实。这里的“站在第0级”就是基线条件“从第n-1级迈一步到第n级”就是递归步骤。只要这两个条件都在递归就不会失控。写递归的时候我习惯先把这两件事写在注释里再动手写代码。很多时候调试半天调不出来回头一看八成是这两个条件没写清楚。2. 阶乘递归的“Hello World”2.1 阶乘的递归实现与执行过程拆解阶乘的数学定义是n! n × (n-1) × (n-2) × ... × 1并且规定0! 1。看它这个定义本身就是递归的形状n! n × (n-1)!。也就是说想求n的阶乘先求(n-1)的阶乘再乘个n就行。用Python写出来几乎和数学公式一模一样def factorial(n): # 基线条件0的阶乘是1 if n 0: return 1 # 递归步骤n! n * (n-1)! return n * factorial(n - 1)JavaScript写法也差不多function factorial(n) { if (n 0) return 1; return n * factorial(n - 1); }我第一次看到这个代码时有个特别大的困惑它怎么能“自动”算完所有乘法后来我把factorial(4)的完整执行过程手写了一遍才彻底明白。假设调用factorial(4)n4不等于0进入递归步骤需要计算 4 * factorial(3)于是调用factorial(3)n3不等于0需要计算 3 * factorial(2)于是调用factorial(2)n2需要计算 2 * factorial(1)于是调用factorial(1)n1需要计算 1 * factorial(0)于是调用factorial(0)n0命中基线条件直接返回1这时候整个调用开始“往回走”factorial(1) 得到 1 * 1 1factorial(2) 得到 2 * 1 2factorial(3) 得到 3 * 2 6factorial(4) 得到 4 * 6 24看到了吗递归其实有“递”和“归”两个阶段。“递”就是一路向下调用把大问题拆小“归”就是当基线条件触发后计算结果一路向上返回最终得到答案。理解这个“先下后上”的过程是吃透递归的重中之重。2.2 递归调用栈函数是怎么一层层“压”进去又“弹”出来的很多初学者不理解为什么factorial(4)调用factorial(3)之后还能记得回来继续算这背后靠的是调用栈Call Stack。你可以把调用栈想象成食堂里一摞洗好的盘子。你用完一个盘子放在最上面下一个用的时候再放在上面要用的时候只能从最上面那个开始拿——这就是“后进先出”。编程语言的函数调用系统就是这么干的每当一个函数被调用系统就往调用栈里压入一个“栈帧”这个栈帧里保存着函数的参数、局部变量、以及“调用完之后该回到哪里”的返回地址。函数执行完毕这个栈帧就被弹出控制权交还给调用方。递归只是“函数调用函数”的特例它一样按这个规则工作。执行factorial(4)时栈底 - [factorial(4)] - [factorial(4), factorial(3)] - [factorial(4), factorial(3), factorial(2)] - [factorial(4), factorial(3), factorial(2), factorial(1)] - [factorial(4), factorial(3), factorial(2), factorial(1), factorial(0)]栈就像叠罗汉一样越叠越高。当factorial(0)返回1时它的栈帧先被弹出接着factorial(1)拿到结果计算出1弹出然后factorial(2)计算……一步步“弹”下去直到栈底只剩下空的调用栈。理解了调用栈你就能明白很多递归的“坑”。比如每个栈帧都要占内存递归层级越深占的内存越多。一旦递归深度超过系统限制比如Python默认大约1000层就会抛出RecursionError。所以递归不是无限可用的它在空间上是有代价的。阶乘这种例子递归深度等于nn一大栈就受不了。这也是为什么后面会出现“非递归”改造这个话题。3. 斐波那契从递归到性能陷阱3.1 朴素递归斐波那契的写法斐波那契数列的规律是第一项和第二项都是1有的定义从0开始那前两项就是0和1从第三项开始每一项都等于前两项之和1, 1, 2, 3, 5, 8, 13, 21……。它同样有一个天然的递归定义fib(n) fib(n-1) fib(n-2)并且fib(1) fib(2) 1。于是新手很容易写出下面这个版本def fib(n): if n 1 or n 2: return 1 return fib(n - 1) fib(n - 2)代码确实简洁和数学定义几乎一一对应。但所有教算法的人都会告诉你这不是一个好的写法。我当时不理解觉得它能跑就行直到我把n从10慢慢加到40发现程序越来越慢最终才意识到问题的严重性。3.2 为什么朴素递归这么慢重复计算的浪费问题出在它“重复计算”太多了。以fib(5)为例它需要算fib(4)和fib(3)算fib(4)又要算fib(3)和fib(2)。注意fib(3)出现了两次每次都要重复计算完整子树。fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ └── fib(1) │ └── fib(2) └── fib(3) ├── fib(2) └── fib(1)从这棵递归树能直观看到fib(2)被重复算了很多次fib(3)也被重复算了。当n变大时这种重复会像瘟疫一样蔓延。用数学可以证明这个朴素递归的时间复杂度是O(2^n)——指数级增长。指数级到底有多可怕用个数看一看就明白了nfib(n)大致值递归调用总次数1055约109次206765约13529次30832040约166万次40102334155约2.04亿次5012586269025约250亿次我自己实测过n40时一个普通的递归版本在笔记本上已经要等好几秒了n50基本就是十几分钟的事了。而迭代版本呢算n500都不费吹灰之力。这就是“会计算”和“算得聪明”的区别。我把这个坑总结成一句话递归写得出来不代表性能能扛得住。使用递归前一定要想一想你写的这个递归到底计算了多少次有没有大量重复子问题。3.3 优化方案记忆化递归与迭代既然问题是重复计算那最直接的思路就是把算过的结果存起来下次直接用。这个方法叫记忆化Memoization在Python里用字典就能实现memo {1: 1, 2: 1} def fib_memo(n): if n in memo: return memo[n] result fib_memo(n - 1) fib_memo(n - 2) memo[n] result return result这样一来每个n只会被真正计算一次。时间复杂度从O(2^n)直接降到O(n)效果立竿见影。我推荐所有递归新手先掌握这个技巧因为它完全保留了递归的“声明式”优点——代码依然很贴近数学定义理解成本低同时解决了性能问题。不过记忆化递归在空间上仍有隐忧它依赖调用栈深度依然可能达到n。对于超大n还可能触发递归深度限制。另一种更“稳”的方案是把递归改成迭代自底向上地算def fib_iter(n): if n 1 or n 2: return 1 a, b 1, 1 for _ in range(3, n 1): a, b b, a b return b这段代码只用两个变量交替更新既没有重复计算也没有深栈风险时间和空间都做到最优。虽然它不再“递归”了但它和递归本质上描述的是同一个递推关系。很多时候递归负责想清楚逻辑迭代负责跑得快跑得稳两者结合使用才是最佳实践。4. 快速排序非递归递归之外的另一种可能4.1 为什么需要非递归快速排序聊完了阶乘和斐波那契这两个经典例子有人可能会问既然递归这么容易出问题那实际业务里怎么处理我拿快速排序来做个扩展。很多人学快速排序时看到的最经典版本就是递归写法def quicksort(arr): if len(arr) 1: return arr pivot arr[0] left [x for x in arr[1:] if x pivot] right [x for x in arr[1:] if x pivot] return quicksort(left) [pivot] quicksort(right)逻辑很简单选一个基准值小的放左边大的放右边然后递归处理左右两边。平均时间复杂度O(n log n)看起来很美。但“看起来美”的前提是递归深度不会爆。要排序n个元素递归深度最坏情况可能会达到n。比如原数组已经基本有序而每次选的基准值又恰好是最大或最小值那左右两边的规模就严重失衡递归栈会非常深。当数据量达到百万级时栈溢出风险就非常现实了。还有一种场景在一些内存受限的嵌入式环境、或者需要严格控制系统运行时栈占用的服务里递归是不被允许的。毕竟每个栈帧都有开销深度不可控不如显式地管理一个“任务队列”。这就是我维护后台服务时赞同“非递归”写法的直接原因——不是递归不好而是它有时不够可控。4.2 用显式栈模拟递归的经典写法非递归快速排序的核心思路是把“系统调用栈”换成“程序自己的栈”。我们不再是调用quicksort来递归处理子数组而是把每个待排序区间的左右边界压入栈中再用while循环不断弹出区间、划分、再压入新区间。下面是一份我实际用过的实现Pythondef quicksort_iterative(arr): # 栈里存的是待处理区间的 (left, right) stack [(0, len(arr) - 1)] while stack: left, right stack.pop() # 区间无效或只剩一个元素跳过 if left right: continue pivot arr[right] # 取最右边作为基准 i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] pivot_index i 1 # 先把右半区间压栈再压左半区间 # 这样先处理左侧后处理右侧逻辑和递归版一致 stack.append((pivot_index 1, right)) stack.append((left, pivot_index - 1)) return arr这里有两个细节要注意。第一个压栈顺序决定了子问题的处理顺序。我先把右区间压进去再把左区间压进去这样弹出来时先处理左区间模拟递归版本的执行路径。如果你希望后进先出地反过来处理就交换两个append的顺序。第二个划分方法用的是Lomuto分区很简单但要注意pivot选最右边元素时循环结束后要把pivot和i1位置交换这样pivot才落在正确位置。这份代码和递归快排完成的事情完全一样每次处理一个区间划分后产生两个更小的区间。但递归深度不再受调用栈限制而是受我们自己分配的stack列表长度限制。只要内存够你甚至可以处理特别大的数组心理上踏实得多。4.3 递归与迭代的取舍思路我从阶乘到快速排序折腾了一圈之后总结了一套自己的取舍经验分享给你优先用递归的场景问题天然具有树形/层级结构比如遍历二叉树、解析JSON、遍历文件目录代码追求可读性和“与问题定义一一对应”并且递归深度可控不会在真实数据上超过系统限制。优先用迭代或显式栈的场景数据规模大或不可预估比如处理几十万级到百万级的数据系统对栈占用有严格要求比如长连接服务、嵌入式环境还有递归树分支多、重复子问题多的情况比如斐波那契的朴素递归。两者之间的折中方案记忆化递归、递归加深度限制参数、递归转尾递归前提是语言支持尾调用优化、或者干脆写成显式栈。很多时候不必二选一而是由一个方案平滑迁移到另一个方案。我在生产项目里就经常先写出清晰递归原型跑通逻辑后再用显式栈或其他迭代方式做性能加固。值得一提的是像LabVIEW这类图形化编程环境里很多人也会习惯性用递归画框图来实现阶乘之类的小功能。但图形化环境下对调用栈的感知更弱更容易出现深度限制问题。我个人建议在LabVIEW中尽量利用循环结构和移位寄存器来实现阶乘和斐波那契它俩的迭代版本都非常简单不必非递归不可。5. 常见问题与排查技巧实录5.1 递归深度过大导致栈溢出这是递归新手最容易撞上的问题。现象很典型程序运行一会儿后报错Python是RecursionErrorJava会报StackOverflowErrorC/C则可能直接段错误。我排查这类问题时第一步不是看代码逻辑而是先确认当前递归的最大深度。Python里可以用sys.getrecursionlimit()查看当前限制默认通常是1000。如果确认是深度问题可以临时调大import sys sys.setrecursionlimit(10000)但记住这只是治标不治本。调大的代价是占用更多内存而且到了某个阈值进程可能被系统杀掉。真正的解决思路是要么减少递归深度比如改用二分递归而不是线性递归要么换成迭代实现。我之前处理一个树形目录统计的需求递归深度恰好是目录深度目录嵌套一深就爆。最后改成显式栈遍历一劳永逸再也不用担心数据把系统压垮。5.2 死循环与基线条件遗漏第二种常见问题是“递归没有停下来的出口”。用户会看到程序卡死CPU占用飙升最后在栈溢出错误中终止。这种问题的元凶往往就是基线条件漏了或写错了。排查手段我建议从三方面入手在递归函数开头打印当前参数观察调用参数是否在向基线条件收敛。列出基线条件覆盖的所有边界场景比如n0、n1、列表为空、树为空这几类情况。重点检查递归调用时传入的参数是否真的比当前参数“更小”。比如factorial(n)里调用factorial(n1)这就南辕北辙了。我见过一个真实的例子同事写递归解析配置忘了处理“配置里嵌套为空对象”的情况结果遇到空对象时递归不终止直接卡死。发现后在函数开头加了一个“如果输入为空则返回空结果”的基线判断问题立刻解决。调试这类问题时日志和打印就是最好的朋友别怕输出多把每一层调用的参数都打出来一眼就能看出问题在哪。5.3 尾递归与编译器优化进阶选手还会碰到“尾递归”这个概念。它指的是递归调用是函数体内最后一条语句且结果直接返回不再参与额外运算。例如def factorial_tail(n, acc1): if n 0: return acc return factorial_tail(n - 1, acc * n)求factorial(5)时这个版本不断累乘acc最后返回120。因为是“尾调用”某些支持尾调用优化Tail Call Optimization简称TCO的语言会复用当前栈帧让递归的栈深度从O(n)降到O(1)。Python官方解释器默认不做尾递归优化Java的JVM也不做。所以指望Python里写尾递归来避免栈溢出是行不通的。但如果是Erlang、Haskell或者开启优化选项的某些Lisp方言尾递归就是性能利器。我的经验是写尾递归本身没有坏处至少它的结构更接近迭代思路清晰。但要不要依赖它的优化效果一定要先翻一下你所用语言的官方文档确认支持后再用。别把“尾递归”和“一定不爆栈”画等号这是很多教程没说清楚的坑。下面整理一个速查表方便你以后遇到问题直接对照症状可能原因排查方向解决方案递归报栈溢出/RecursionError递归深度超过限制打印参数确认深度级数调大限制临时改用迭代或显式栈程序卡死CPU占满基线条件遗漏或参数不收敛打印每层调用参数审查基线条件补全基线条件确保参数向出口收敛栈溢出但在递归外层调用栈本身过大或函数体占用栈空间过多用profiler定位栈帧比较大的函数减少局部大数组分配或改迭代实现计算结果正确但极慢存在大量重复子问题画出递归树统计相同子问题的出现次数使用记忆化或迭代函数返回值与预期不符基线条件返回值不正确用最小输入如n0、n1单测修正基线条件的返回值6. 写在最后的体会折腾完阶乘、斐波那契再到快速排序的非递归改造我最大的体会其实是递归本身并不复杂复杂的是你能否“看见”它在你机器上的一举一动。调用栈、栈帧、重复子问题这些词看懂容易真正建立体感很难。我的建议很朴素遇到一个递归题别急着敲代码先拿出一张纸把n5或n4的执行过程一步步画出来。画过几次之后你对递归的理解就会上一个台阶。还有一点经验不要死记“递归一定比迭代好”或“迭代比递归好”这种绝对结论。我实际项目里能写出让同事一眼看懂的递归就比一个绕来绕去的迭代更有价值当性能测试表明递归成为瓶颈时再去改迭代也不迟。先想清楚再动手这才是写代码的从容。希望这篇梳理能帮你在递归这条路上少踩一些我当年踩过的坑。