Python 中的递归合并排序和堆栈帧

Question

以下代码（不是我的，只是研究它）在递归原始列表（即 list_）和合并例程之间（正确地）反弹。堆栈帧的流程（即，即使在 Python Tutor 中观看时，它们如何以及为何返回它们的方式也不清楚，这就是我在下面叙述的内容）。代码 returns 和问题如何遵循程序的描述。

def merge(left, right):
    if not len(left) or not len(right):
        return left or right

    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j+= 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break 

    return result

def mergesort(list_):
    if len(list_) < 2:
        return list_

    middle = len(list_)//2
    left = mergesort(list_[:middle])
    right = mergesort(list_[middle:])

    return merge(left, right)


list_ = [7,5,2,1,3]

print(mergesort(list_))

我们命中的第一个递归调用是left（我们要对列表的左半部分进行排序，然后对左半部分的左半部分进行排序，等等，直到我们得到一个列表的大小一个并击中基本情况）。这很好用。我们从 [7,5,2,1,3] 到 [7,5] 再到 [7] 并达到基本情况。到目前为止，一切都很好。 我希望堆栈帧开始返回，但事实并非如此。我认为是 returns 7，但随后我们跳转到下一组递归调用 right。 5 再次出现。 5 出现在 7 之前的堆栈帧中，因此返回的顺序相反（这很好）。新参数将 5 分开并创建一个列表，从而引发基本情况并返回 5。

这就是它变得奇怪的地方：程序进行到合并步骤，这是正确的。如何 "know" 跳过对 right 或 left 的进一步递归（我给了它一个完整的列表，其中大部分是未触及的）并跳转到合并？此外，它如何知道在没有明确指示的情况下从合并返回到合并排序函数，并确切知道从哪里开始？任何人都可以阐明这一点吗？传统算法文本和大多数视频的帮助为零，因为它们不涉及堆栈框架。

Answer 1

我认为您的困惑与不了解每个堆栈帧都有其自己的执行点有关。每次调用函数时，框架的执行都会暂停，并为函数调用创建一个新框架。当它 returns 时，前一帧从它停止的地方开始。 "knows" 代码下一步应该放在哪个中心位置，每个级别都自行处理。

在您描述的示例场景中，mergesort 对 [7, 5] 的调用首先将列表拆分为 [7] 和 [5]，然后在每个列表中递归转得到left和right。当这些递归调用中的第二个返回时，它继续执行代码的下一部分，即 merge 调用，因为这就是代码中的下一个部分。

你可以很清楚地看到逻辑，就在这里：

left = mergesort(list_[:middle])
right = mergesort(list_[middle:])

return merge(left, right)

这告诉你在这个运行上（以及每个没有达到基本情况的运行），它将递归两次然后 merge.

Python 中的递归合并排序和堆栈帧

Recursive Merge sort and Stack Frames in Python

python

recursion

merge

mergesort