递归一个在编程入门阶段必讲、但很多人到工作两三年后依然说不清的概念。网上讲递归的文章一大把大部分都在强调递过去、归回来这六个字可你会背这六个字照样写不出一个像样的递归函数。我这篇不打算重复那套说教我想把递归这件事拆到不能再细函数调用栈到底是什么、递归运行时发生了什么、经典的快速排序递归怎么写、怎么一步步改成非递归以及面试和实战里最常踩的坑。看完这一篇递归和快排非递归这些问题你基本就能在心里一次性理清。这篇内容的定位是给两种人看一是刚学完编程基础、被递归折腾得头疼的新人二是自认为会用递归、但说不太清底层原理、遇到栈溢出只能靠加递归深度上限糊弄过去的开发者。两种人都会在下面找到自己需要的东西——前者的重点在理解模型和执行过程后者的重点在快排非递归的完整落地和通用改写方法论。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, 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]循环递推版本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, acc0): 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, depth0): 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 的时候我先问自己三个问题问题规模在缩小吗终止条件是否覆盖了所有最小情况每一层递归的返回值链路是否完整这三个问题能过滤掉绝大多数问题。最后再分享一个我个人的习惯写递归前永远先在小规模输入上手动模拟一遍。模拟的时候只算前两层后面靠规律推导而不是硬算到底。那些把递归想得太玄乎的人往往是因为从一开始就没有亲手跑过一个完整的调用过程。递归真的不是魔法它就是一只看不见的手在帮你压栈弹栈而你一旦把这只看不见的手画出来递归和非递归之间的那条鸿沟自然就消失了。