归并排序函数的递归令人困惑

我理解递归的基本原理，并且在处理简单的事情时，例如计算数字的阶乘（这是递归的最基本用法），并不会造成混淆。但是，当您在更复杂的环境中开始使用递归时，它开始变得对我非常困惑。归并排序函数的递归令人困惑

在我的情况，我想创建一个函数，它使用“合并排序”的方式来排序列表中的项目，使用递归。所以我开始工作，这就是我想出了在我第一次尝试（不是真的，我不得不修正了一些错别字）：

def merge_sort(ls): 
    size = len(ls) 
    if size <= 1: 
    return ls 
    left = merge_sort(ls[:size/2]) 
    right = merge_sort(ls[size/2:]) 
    return merge(left, right) 

def merge(left, right): 
    ls = [] 
    ln1 = len(left) 
    ln2 = len(right) 
    length = ln1 + ln2 
    while length > 0: 
    if not left: 
     ls.append(right.pop(0)) 
     length -= 1 
    elif not right: 
     ls.append(left.pop(0)) 
     length -= 1 
    else: 
     if left[0] < right[0]: 
     ls.append(left.pop(0)) 
     length -= 1 
     elif right[0] < left[0]: 
     ls.append(right.pop(0)) 
     length -= 1 
    return ls 

print merge_sort([8,5,4,6,1])

我点击运行，它的工作，但我不明白为什么它作品。是的，我创建了一段代码来完成所要做的事情，但我不明白为什么。

所以“merge_sort”将列表拆分为两部分，直到有一个简单的列表与单个项目。它使用递归来实现这一点，当我们得到一个单一项目的简单列表时，它将它分配给一个新列表，即左侧或右侧。然后，我使用“合并”函数中的这两个新列表对它们进行排序，并以正确的方式将它们合并在一起。到目前为止这么好，但是当我点击“执行”时我期待的是让代码在前两项停下来，并打印一份包含2个已排序项目的小列表。然而“merge_sort”继续前进。即使我相信它应该在执行后结束：

return merge(left, right)

现在这是我的问题。为什么它会返回到“merge_sort”的开始，以及它如何保存旧值而不会破坏由“合并”生成的新排序“小列表”我希望我的问题对你有意义。

谢谢你们的帮助！

来源

2017-06-20 Teabx

这听起来像你问一个[调用堆栈]（https://www.youtube.com/watch?v=Q2sFmqvpBe0），或者更具体地说在这种情况下，[递归堆栈]（https）：//www.youtube.com/watch v = ygK0YON10sQ）？阅读关于它们了解这里进行的递归。 – LismUK

直到最初的'merge_sort（[8,5,4,6,1]）'调用返回，才会打印出来。但在此之前，两个子列表中的两个'merge_sort'必须返回。但是在_that_发生之前，每个这些子列表的子列表中的“merge_sort”必须返回。等等，直到您找到零个或一个元素子列表的基本情况。顺便说一句，如果你想在包含重复项目的列表上安全地使用它，你的算法需要调整。考虑'left [0] == right [0]'时会发生什么。 –

这个问题的答案相当广泛。为了完全理解这一点，你需要了解stackbuildup如何与递归协同工作，以及这个buildup中的指针是如何工作的。

这是递归调用的，因为列表需要通过将它分成一半来分解，直到它处于最小可能单位（1或0的余数）为止。一旦完成，堆栈累积将使用其预定义的指针追溯所有以前的呼叫实例。

这是一个深入细致的编程语言概念。

欲了解堆栈堆积和回调参考这里的更多信息。 https://en.wikipedia.org/wiki/Call_stack

来源

2017-06-20 15:59:28

我想我现在得到它。这就像为列表中的每个值创建该函数的其他变体，直到每个值都取最终值。说实话www.pythontutor.com帮助我弄清楚那里发生的事情，但我现在更加“明白”了一下。感谢您的帮助 – Teabx

归并排序函数的递归令人困惑

回答

相关问题