“递归算法”这四个字，几乎所有写程序的人都听过，也都能背出那句标准解释：函数通过调用自身来解决问题。但说句实话，我见过太多“背得出定义却写不出代码”的情况——真到要动手设计一个递归函数时，脑子里的疑问接踵而至：函数怎么能调用自己？调用时当前这层的数据会不会被覆盖？递归和死循环到底有什么区别？
这篇文章就把这些问题一次说透。我会从“函数调用自身”在计算机底层到底发生了什么讲起，再用几个经典案例把递推和回归的过程拆开看，接着聊递归与迭代的取舍，最后复盘我在真实项目里踩过的三个递归坑，以及几个能直接拿去做生产环境的改造思路。不管是刚开始学编程的初学者，还是写了两三年代码、想把递归这套东西系统梳理一遍的开发者，这篇应该都能给你有用的参考。
1. 递归的本质：函数调用自身背后那套“栈”机制
1.1 当函数调用自己时，计算机到底在做什么
很多人对递归的第一个误解是：函数调用自身，是不是相当于把函数复制了一份？不是。代码永远只有一份，运行时只是用不同的栈帧去执行它。
函数调用的本质是压栈和弹栈。不管是调用其他函数还是调用自己，运行时都要做三件事：把当前函数的执行状态（参数、局部变量、返回地址）打包成一个栈帧，压进制调用栈；跳转到被调用函数的代码处开始执行；等被调用函数执行完，再把旧栈帧弹出，继续原有流程。
所以当 factorial(n) 内部执行 factorial(n-1) 时，并不是“我消失了，换新我来跑”，而是“我先挂起，等新我这个函数实例算完，再拿结果继续我自己的工作”。“等回来继续工作”这半句话，是理解递归的关键。调用栈里每一层都保存着自己那份 n 和返回位置，彼此完全隔离。用一个生活化的比喻：这就像一摞便签，每记一层就压在上面，做完一层撕掉一层，拿到底层答案后再一层层倒推回去。
喵一眼下面这个最简单的递归函数：
PYTHON
复制
1
def factorial(n):
2
if n <= 1:
3
return 1
4
return n * factorial(n - 1)
在 factorial(4) 执行过程中，调用栈是这样的：
调用顺序
当前栈帧
执行的动作
需要等待
1
factorial(4)
return 4 * factorial(3)
factorial(3)
2
factorial(3)
return 3 * factorial(2)
factorial(2)
3
factorial(2)
return 2 * factorial(1)
factorial(1)
4
factorial(1)
n <= 1，直接返回 1
-
前 4 步是“递进”，不断往下压栈。等到 factorial(1) 返回 1 之后，开始“回归”：factorial(2) 拿到 1，算 2×1=2；factorial(3) 拿到 2，算 3×2=6；factorial(4) 拿到 6，算 4×6=24。所有压进去的栈帧依次弹出，这就是递归完整的生命周期。
这里多提一句很多人在搜的“函数声明”和递归的关系。递归函数从声明角度来看，其实就是一个普通函数，只不过函数体内出现了对自身的引用。在 Python 这类解释型语言里，函数名在函数体内部就已经完成绑定，所以自我引用完全合法，不需要任何特殊标记。
还有一个容易被忽略的细节：调用栈空间是有限的。系统给一个线程分配的栈空间通常只有 1MB 到 8MB，递归每压一层栈帧就占一点空间。压得太深，栈空间耗尽，就会报 StackOverflowError 或 RecursionError。这个概念后面第 4 章踩坑部分还会继续展开。
1.2 基例与递推步骤：递归的两个“安全锁”
既然每压一层栈帧都不会在返回前释放，递归就必须有停下来的机制。递归有两个核心要素：基例（base case）和递推步骤（recursive step）。基例就是问题小到可以直接返回答案的出口；递推步骤就是把当前问题拆成更小规模的同类问题，通过函数调用自身继续求解。
判断一个递归函数写没写对，可以问自己两个问题：
最简单的情况下，函数能不能直接返回答案而不再调用自己？
每次递归调用，参数是不是在朝基例的方向收拢？
以 factorial 为例，if n <= 1: return 1 是基例；return n * factorial(n-1) 里的 n-1 让参数单调递减，最终一定会撞上基例。这两个条件缺一个都不行。
可以这样理解递归：它有点像反向的数学归纳法。你先假定一个更小规模的同类问题已经被正确解决，然后站在它的肩膀上解决当前问题；至于那个更小规模的问题为什么能被解决，因为不断缩小之后，总会被一个平凡的基例接住。很多初学者会把递推步骤写成 n+1，导致参数离基例越来越远，程序跑起来直接卡死然后栈溢出，这种错误本质上是第二个问题没想清楚。
2. 三个经典递归案例：从最小模型到实战场景
2.1 阶乘：最