合并排序函数的递归很混乱
我理解递归的基本原理，并且在处理简单的事情时不会感到困惑，例如计算数字的阶乘，这是递归的最基本用法。 但是，当您在更复杂的环境中开始使用递归时，它开始变得对我非常困惑。
在我的情况下，我想创建一个函数，它使用“合并排序”方式使用递归对列表中的项目进行排序。 所以我开始工作了，这就是我第一次尝试时想到的（不是我必须修正一些错别字）：
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”的开头，它如何保存旧值而不会搞乱由“merge”生成的新排序“小列表” ？ 我希望我的问题对你有意义。
谢谢你们的帮助！
这个答案是相当广泛的。 为了完全理解这一点，你需要了解stackbuildup如何与递归协同工作，以及这个buildup中的指针是如何工作的。
这是递归调用的，因为列表需要通过将它分成一半来分解，直到它处于最小可能的单位（余数为1或0）。一旦完成，堆栈建立将使用其预定义的指针来追溯所有的先前的呼叫实例。
这是一个深奥的编程语言概念。
欲了解更多关于栈堆积和回调参考信息。 https://en.wikipedia.org/wiki/Call_stack
链接地址: http://www.djcxy.com/p/53493.html