递归，一个在编程入门阶段必讲、但很多人到工作两三年后依然说不清的概念。网上讲递归的文章一大把，大部分都在强调"递过去、归回来"这六个字，可你会背这六个字，照样写不出一个像样的递归函数。我这篇不打算重复那套说教，我想把递归这件事拆到不能再细：函数调用栈到底是什么、递归运行时发生了什么、经典的快速排序递归怎么写、怎么一步步改成非递归，以及面试和实战里最常踩的坑。看完这一篇，递归和快排非递归这些问题，你基本就能在心里一次性理清。
这篇内容的定位是给两种人看：一是刚学完编程基础、被递归折腾得头疼的新人；二是自认为会用递归、但说不太清底层原理、遇到栈溢出只能靠加递归深度上限糊弄过去的开发者。两种人都会在下面找到自己需要的东西——前者的重点在理解模型和执行过程，后者的重点在快排非递归的完整落地和通用改写方法论。
1. 为什么递归总是"一看就懂，一写就废"
1.1 递归的本质：不是"自己调用自己"这么简单
很多人对递归的理解停留在"函数在函数体里调用自己"。这句话对，但没有解释任何东西。递归的真正本质是：一个大问题被分解成若干个结构完全相同的更小问题，直到小到可以直接给出答案为止。
拿俄罗斯套娃来类比，一个套娃打开，里面是一个更小的套娃，再打开，又是一个更小的套娃，直到最小的那个实心套娃无法再打开。你要数清总共有几个套娃，做法就是"打开一个，数 1，然后重复同样的动作去处理里面那个更小的"。递归函数做的就是这个事情。
更重要的是，递归函数其实每次调用自己时，每次使用的都是同一个函数代码，但每次拥有独立的变量空间。这一点必须刻进脑子里，否则后面读递归执行过程必晕。
1.2 递归三要素：终止条件、递推关系、缩小规模
我写递归的时候，会在脑子里强制过三关：
- 终止条件（base case）：问题小到什么程度时，我可以直接返回答案，不再继续调用？
- 递推关系（recursive relation）：当前问题的答案，怎么由更小规模问题的答案组装出来？
- 规模缩小（progress）：每次递归调用，参数是否严格向着终止条件靠近？
这三个要素缺一不可。缺了终止条件，函数无限调用，直接把调用栈撑爆；递推关系写错，返回结果牛头不对马嘴；规模没缩小，其实就是缺少终止条件的另一种表现，本质上还是死循环递归。
一个最经典的例子，计算阶乘 n!：
def factorial(n): # 终止条件 if n == 1: return 1 # 递推关系：n! = n * (n-1)! return n * factorial(n - 1)这里n - 1就是规模缩小，n == 1就是终止条件，n * factorial(n - 1)就是递推关系。函数本身只有短短几行，但它的执行过程值得拆开来看，这就是下一章要做的事。
2. 拆解递归的执行过程：从栈帧到调用栈
2.1 递归函数进入和退出的完整流程
很多教材会告诉你"调用栈"这个概念，但你真正理解它，是看一场完整的调用流程之后。以factorial(4)为例，我一步步写给你看。
第一次调用factorial(4)时，系统在调用栈上压入一个栈帧，栈帧里保存了参数n = 4、返回地址、局部变量等信息。进入函数体后，发现n != 1，于是执行4 * factorial(3)。注意：先要计算factorial(3)才能乘 4，所以factorial(4)的栈帧不能弹出，必须留在栈里等着。
于是系统压入第二个栈帧，参数n = 3。同样的逻辑，又压入第三个栈帧n = 2，再压入第四个栈帧n = 1。
当n = 1这个栈帧执行时，命中终止条件，直接返回 1，这个栈帧弹出。返回值交给上一层的factorial(2)，它计算2 * 1 = 2，弹出自己的栈帧。返回值再交给factorial(3)，计算3 * 2 = 6。再交给factorial(4)，计算4 * 6 = 24，弹出最后一个栈帧。
所以整个调用栈的过程是：
factorial(4) |-> factorial(3) | |-> factorial(2) | | |-> factorial(1) | | | 返回 1 | | 返回 2 * 1 = 2 | 返回 3 * 2 = 6 返回 4 * 6 = 24这个缩进图你一定要自己动手画一遍。画完你会发现，递归的"递"就是逐层压栈，"归"就是逐层弹栈并计算结果。整个过程和"函数 A 调用函数 B，函数 B 调用函数 C"没有任何本质区别，只不过 A、B、C 恰好都是同一个函数而已。
2.2 栈溢出的成因与递归深度的工程边界
既然递归只是压栈弹栈，那"栈溢出"就不难理解了：每次调用压入一个栈帧，如果递归深度太大，调用栈的空间被耗尽，程序就被迫终止。Python 里默认的递归深度限制通常是 1000 左右，超过就会抛出RecursionError。
有人试图用sys.setrecursionlimit(1000000)把限制调大，然后继续跑深递归。这样做在测试环境偶尔能撑住，但生产环境我不建议你这么玩。原因有两个：
- 栈空间是有限的，调高限制只是推迟崩溃，而且容易导致进程直接段错误（segmentation fault），而不是给你一个优雅的 Python 异常。
- 深递归本身的性能也很差，每一次函数调用都有额外的开销：压栈、弹栈、参数拷贝、返回地址维护。
所以递归深度这道坎，不是改参数能绕过去的，要么换非递归写法，要么用尾递归优化，要么用动态规划自底向上改。后面讲快排非递归时，你会看到我们是怎么绕开这道坎的。
3. 递归实战套路：从斐波那契到全排列，建立"分而治之"的脑回路
3.1 斐波那契数列的递归实现与性能陷阱
斐波那契数列是递归教科书必讲案例：
def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)代码极短，可读性极好，但它有一个严重问题：重复计算。
当n = 5时，调用fib(4)和fib(3)。而fib(4)又会调用fib(3)和fib(2)。这里的fib(3)被计算了两次，fib(2)被计算了三次。随着n增大，重复调用是指数级增长的，复杂度大约 O(2^n)。fib(40)就已经慢得肉眼可见，fib(50)在普通机器上可能要跑很久。
解决思路有两个：加缓存做备忘录（memoization），或者改成循环递推。
备忘录版本：
def fib_memo(n, memo=None): 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]循环递推版本：
def fib_iter(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b这里我想说一个观点：递归不是用来炫技的，它是用来让代码与问题本身的结构对齐。斐波那契的数学定义本身就是递推的，所以递归写法天然匹配定义，但工程上我们还是会优先选循环版本。
3.2 全排列的递归思维：回溯的雏形
全排列是另一个经典题目，给你一个数组[1, 2, 3]，输出所有排列。它的递归写法特别能体现"状态选择"的思想。
def permute(nums): result = [] used = [False] * len(nums) path = [] def backtrack(): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) backtrack() used[i] = False path.pop() backtrack() return result这里的关键不是看代码本身，而是体会递归内的"选择-递归-撤销选择"这个循环。path.append就是选择，backtrack()就是进入更深的决策层，path.pop()和used[i] = False就是回溯复位。递归在这里负责维护多层嵌套循环的状态，你如果用普通的 for 循环写全排列，需要写 N 层嵌套，根本无法通用；而递归让嵌套深度变成了动态的。
这个案例告诉你一件事：当问题的复杂度体现在"嵌套层数不确定"时，递归往往是最自然的表达方式。
4. 快速排序的递归实现：分治思想的集大成者
4.1 快排的分区逻辑与递归主框架
快排的核心思想是分治：选一个基准值，把数组分成小于基准和大于基准两部分，然后递归地对两部分排序。
我推荐用 Lomuto 分区法，代码简洁，容易理解：
def partition(arr, left, right): 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] return i + 1这个分区的逻辑是：遍历[left, right)区间，把所有小于 pivot 的元素换到左边，i始终指向最后一个小于 pivot 的元素的位置，最后把 pivot 放到i + 1的位置上。此时 pivot 已经排到了正确的位置，接下来递归去处理它左右两侧的子区间。
递归主框架：
def quick_sort(arr, left, right): if left >= right: return pivot_idx = partition(arr, left, right) quick_sort(arr, left, pivot_idx - 1) quick_sort(arr, pivot_idx + 1, right)为什么递归终止条件是left >= right？因为当区间里没有元素（left > right）或只有一个元素（left == right）时，它天然有序，不需要继续处理。
整个思想可以用一句话概括：每次让一个元素落到最终位置，然后缩小问题规模，重复同样的操作。
4.2 快速排序的时间复杂度与递归深度
快排的平均时间复杂度是 O(n log n)，但这不是重点，重点是递归深度带来的栈压力。
理想情况下，每次 partition 都能把数组分成两半，那么递归深度是 O(log n)，大约 1000 个元素只需要 10 层左右的递归，非常安全。
最坏情况下，比如数组已经是有序的，而 pivot 每次选到最大或最小元素，分区严重不平衡，一边为空，另一边几乎全量。这时递归深度是 O(n)，也就是说对 100 万元素排序可能递归 100 万层，直接栈溢出。
所以纯递归快排在工程上是有隐患的。很多教材不会告诉你这个细节，但面试官往往就等在这里："你能把快排写成非递归吗？"——他要的就是你用显式栈替代系统调用栈。
5. 快速排序非递归实现：手写栈模拟函数调用栈
5.1 核心思路：把"待处理的子区间"压入显式栈
递归快排做的事情，本质上就是用系统调用栈记录"还需要排序的子区间"。我们手动做一个栈，把子区间边界[left, right]压入栈中，循环弹出、分区、再压入新的子区间，循环往复直到栈为空。
为什么用栈而不是队列？其实都可以，栈是 LIFO，先处理后压入的区间，队列是 FIFO，按顺序处理，两者最终都能完成排序，只是处理顺序不同、CPU 缓存局部性不同。但既然我们要模拟的是"函数调用栈"，用栈更贴合原语义，也更容易让人理解。
5.2 完整代码与执行过程逐行分析
def quick_sort_iterative(arr): if len(arr) <= 1: return arr stack = [(0, len(arr) - 1)] while stack: left, right = stack.pop() if left >= right: continue pivot_idx = partition(arr, left, right) # 压入左子区间 if pivot_idx - 1 > left: stack.append((left, pivot_idx - 1)) # 压入右子区间 if pivot_idx + 1 < right: stack.append((pivot_idx + 1, right)) return arr用一个例子走一遍。假设arr = [5, 3, 8, 4, 2]。
初始stack = [(0, 4)]。
第一次循环，弹出(0, 4)，调用partition(arr, 0, 4)，pivot 选arr[4] = 2，分区结果是[2, 3, 8, 4, 5]，返回pivot_idx = 0。
左边区间(0, -1)无效，不压栈。右边区间(1, 4)压入栈。
第二次循环，弹出(1, 4)，对[3, 8, 4, 5]分区，pivot 选5，结果变成[3, 4, 2, 5, 8]的局部调整，整体数组为[2, 3, 4, 5, 8]，返回pivot_idx = 3。
左边区间(1, 2)压入栈，右边区间(4, 4)无效不压栈。
第三次循环，弹出(1, 2)，对[3, 4]分区，返回pivot_idx = 2，两边区间都无效，不压栈。
栈空，排序完成。
这个过程的关键点在于压栈前的两个if判断：只有当子区间长度大于 1 时才压栈。这个判断直接决定了循环能不能终止。你如果忽略了它，就会把一个空区间无限压栈弹出，死循环跑不完。
5.3 非递归快排的血泪经验
第一，栈里存的是元组(left, right)，千万别只存数组下标总数。我见过有人图省事只存数组长度，结果搞不懂到底该处理哪个区间，代码越改越乱。边界这种东西，一个元组清清楚楚。
第二，partition传入的left、right要和上次递归快排完全一致。很多人写递归的时候边界是闭区间[left, right]，改成非递归之后还是闭区间，那就必须保证压入的也是闭区间端点。混用半开半闭区间是 bug 重灾区，我建议你在心里把区间定义为"包含两端"的闭区间，整套代码统一。
第三，相比递归版本，非递归快排的运行速度不一定更快。它只是把系统栈换成了堆上的数组，摆脱了栈深度限制，但多了一道手动管理数据结构的工作。衡量它的价值在于稳定性和可控性，而不是性能上的绝对优势。
6. 递归转非递归的通用方法论
6.1 三种常见改写套路
前面讲快排非递归只是方法论的一个应用实例，现在把通用套路总结出来，你会发现递归转非递归其实有章可循。
套路一：尾递归直接改循环。
尾递归指递归调用是函数的最后一个操作，函数的返回值直接就是递归调用的返回值，不需要再参与后续计算。比如：
def sum_to(n, acc=0): if n == 0: return acc return sum_to(n - 1, acc + n)这种写法本质上就是循环，直接改成：
def sum_to_iter(n): acc = 0 while n > 0: acc += n n -= 1 return acc套路二：普通递归用显式栈模拟。
快排就是这个套路的典型。核心工作是明确"递归状态"是什么。快排递归状态就是子区间边界，所以栈里存边界。全排列递归状态更复杂一点，可能需要存当前路径，所以栈里存路径快照。抽象地说，你只需要把递归函数的每个参数打包成元组，压入栈中，循环出栈处理即可。
套路三：自底向上替代递归。
很多递归问题本质上是从大问题往下拆，但如果你能明确知道最小子问题的答案，就可以反过来从底部往上推。斐波那契的循环版本就是这类。这个思路和动态规划的重叠子问题一脉相承。
6.2 什么场景值得改，什么场景不值得改
我的判断标准很简单：
- 递归深度可能超过几千、上万的，必须改。
- 递归深度只有几十、几百的，比如目录树遍历，保留递归完全没问题，代码还清晰。
- 递归逻辑极其复杂，比如解析嵌套 JSON、树形结构遍历，强行改非递归只会让代码失去可读性，如果不是栈溢出的硬约束，我不建议改。
- 面试被问到非递归写法时，既要写得出，也要能说出"什么情况下选非递归"的判断标准，这才是加分项。
7. 递归调试三板斧：打印、缩进、边界检查
7.1 用缩进打印递归调用轨迹
调试递归和调试普通循环完全不同。普通代码的 bug 靠断点一步步看能定位，递归的 bug 往往藏在整个调用链里，单步看容易看丢。我最常用的方法是在函数入口打印参数，退出时打印返回值，并用缩进代表递归深度。
def factorial_debug(n, depth=0): indent = " " * depth print(f"{indent}enter factorial({n})") if n == 1: print(f"{indent}return 1 (base case)") return 1 result = n * factorial_debug(n - 1, depth + 1) print(f"{indent}return {result}") return result factorial_debug(4)运行结果：
enter factorial(4) enter factorial(3) enter factorial(2) enter factorial(1) return 1 (base case) return 2 return 6 return 24看到这个输出，你马上能定位几件事：有没有进入终止条件、返回值是否按预期逐层传递、有没有出现该返回却一直往下调用的死循环。
7.2 几个高频递归 bug 与排查思路
我整理了这几类，每一类都在实际代码评审中见过：
- 终止条件漏写或写错位置：比如快排里面用
if left > right而不是if left >= right，单元素区间还在递归，活活把栈撑爆。 - 递归参数没有向终止条件收敛：比如
fib(n - 1) + fib(n - 2)中某个分支传了n本身，永远不减小。 - 返回值被吞掉：递归函数里只调用但不
return，导致上一层拿到None。这种 bug 特别隐蔽，因为不崩，但结果全错。 - 共享可变对象污染：全排列里
path[:]漏掉了[:]，直接在 result 里存同一个列表引用，最后所有结果都一样。这类问题本质上不是递归逻辑错，而是 Python 可变对象的引用问题，但递归场景特别容易犯。
排查递归 bug 的时候，我先问自己三个问题：问题规模在缩小吗？终止条件是否覆盖了所有最小情况？每一层递归的返回值链路是否完整？这三个问题能过滤掉绝大多数问题。
最后再分享一个我个人的习惯：写递归前永远先在小规模输入上手动模拟一遍。模拟的时候只算前两层，后面靠规律推导，而不是硬算到底。那些把递归想得太玄乎的人，往往是因为从一开始就没有亲手跑过一个完整的调用过程。递归真的不是魔法，它就是一只看不见的手在帮你压栈弹栈，而你一旦把这只看不见的手画出来，递归和非递归之间的那条鸿沟，自然就消失了。
