递归函数遇到自调用时如何运作？以Python合并排序为例

所有语言的递归自调用，都不会像你理解的那样“跳回函数开头覆盖之前的执行进度”，它依赖函数调用栈来保存每一次执行的现场：

• 程序每调用一次函数（不管是调用别的函数，还是调用函数自己），都会把当前执行的状态打包成一个独立的「执行帧」压入栈顶。执行帧里会存：当前函数的参数值、局部变量、当前代码执行到了哪一行，等当前调用结束后要从哪一行继续执行。
• 被调用的新函数会完全独立运行，和外层的函数没有执行流的重叠，不会打断外层的执行进度。
• 当被调用的函数运行结束返回结果时，对应的执行帧会从栈顶弹出，程序回到之前保存的外层状态，把返回值赋值给对应的变量，接着往下执行。

拿你提供的测试输入[2, 5, 3, 8, 6, 9, 1, 4, 7]举例子，每一步的执行顺序是完全线性可追溯的：

1. 第一次进入mergesort，接收到完整的9元素列表，计算出midpoint=4，此时准备执行left = mergesort(lst[:midpoint])
2. 先把当前层的所有状态压栈：参数是9元素列表、midpoint值是4、执行位置停在这行赋值语句，等返回了要接着处理right部分
3. 把切出来的左半片段[2,5,3,8]作为新参数，启动一个全新的mergesort实例
4. 这个新的mergesort实例继续重复上面的流程：拆成两半、压当前状态、调用更内层的mergesort，直到某一层的列表长度<=1，不需要再拆分，直接把自己的列表返回
5. 每一层的mergesort拿到左右两个已经排序好的子列表后，会完成合并，把合并后的结果返回到上一层，对应执行帧出栈，上一层拿到结果后赋值给对应的left/right变量，继续执行后续的合并逻辑

你之前的误解核心是把递归等同于循环式跳转：递归的执行完全不是类似for循环的“反复跳回起点重复执行”。它是一个嵌套压栈、逐层出栈的过程：先一路拆到最细的不可再分的单元（长度为1的列表），再从最内层开始逐层往回合并结果，整个过程的每一步状态都被栈结构完整保存，不会出现混乱的跳转。

这段节选的课程代码的合并逻辑有明显疏漏：

• 在if left[0] < right[0]的分支中，只把left[0]加入了新列表，但没有执行del left[0]操作，会导致循环永远重复读取left的第一个元素，触发死循环
• 正确的逻辑需要在两个分支里，都对已经取走的元素做删除操作，保证两个列表的元素同步前移。

内容的提问来源于stack exchange，提问作者Farhad Tahmasebi