我是新手程序员
我正在查找一个使用递归函数的问题。虽然我可以理解要点，但有一个不清楚的问题，我在调试过程中无法立即破译。我将感谢您对我的问题的帮助。
问题的概念(合并排序)非常简单，但我对递归函数的工作方式感到困惑。Bellow是我正在处理的程序(来自Georgia Tech的Python课程)：
def mergesort(lst):
if len(lst) <= 1:
return lst
else:
midpoint = len(lst) // 2
left = mergesort(lst[:midpoint])
right = mergesort(lst[midpoint:])
newlist = []
while len(left) and len(right) > 0:
if left[0] < right[0]:
newlist.append(left[0])
else:
newlist.append(right[0])
del right[0]
newlist.extend(left)
newlist.extend(right)
return newlist
print(mergesort([2, 5, 3, 8, 6, 9, 1, 4, 7]))
问：当程序到达此行left = mergesort( lst[:midpoint])时会发生什么？
根据我的理解，它返回到程序的第一行，然后再次下降以达到同一行(就像for一样)。
所以它不断返回!!但是，这使我无法读取该程序。一般来说，程序如何处理递归函数是我的主要问题。我无法理解它的工作方式。
当程序到达此行时会发生什么
left = mergesort(lst[:midpoint])？根据我的理解，它返回到程序的第一行，然后再次下降以达到同一行......
每次程序重复出现时，它都会使用较小的列表调用mergesort。我们称之为"子问题"——
def mergesort(lst):
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # find midpoint
left = mergesort(lst[:midpoint]) # solve sub-problem one
right = mergesort(lst[midpoint:]) # solve sub-problem two
# ...
例如，如果我们第一次使用 4 元素列表调用mergesort-
mergesort([5,2,4,7])
输入列表lst不符合基本情况，因此我们转到else分支 -
def mergesort(lst): # lst = [5,2,4,7]
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # midpoint = 2
left = mergesort(lst[:midpoint]) # left = mergesort([5,2])
right = mergesort(lst[midpoint:]) # right = mergesort([4,7])
# ...
请注意，调用mergesort时存在[5,2]和[4,7]子问题。让我们对第一个子问题重复这些步骤 -
left = mergesort([5,2])
def mergesort(lst): # lst = [5,2]
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # midpoint = 1
left = mergesort(lst[:midpoint]) # left = mergesort([5])
right = mergesort(lst[midpoint:]) # right = mergesort([2])
# ...
所以它不断返回!!
不完全是。当我们解决此步骤中的子问题时，情况看起来有所不同。当输入是一个元素或更少时，满足基本情况并且函数退出 -
left = mergesort([5])
def mergesort(lst): # lst = [5]
if len(lst) <= 1: # base case condition satisfied
return lst # return [5]
else:
... # no more recursion
递归停止left子问题，并返回[5]的答案。这同样适用于right子问题 -
right = mergesort([2])
def mergesort(lst): # lst = [2]
if len(lst) <= 1: # base case condition satisfied
return lst # return [2]
else:
... # no more recursion
接下来我们返回第一个left子问题 -
left = mergesort([5,2])
def mergesort(lst): # lst = [5,2]
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # midpoint = 1
left = mergesort(lst[:midpoint]) # left = [5] <-
right = mergesort(lst[midpoint:]) # right = [2] <-
# ...
return newlist # newlist = [2,5]
现在，您将对第一个right子问题重复这些步骤 -
right = mergesort([4,7])
def mergesort(lst): # lst = [4,7]
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # midpoint = 1
left = mergesort(lst[:midpoint]) # left = mergesort([4])
right = mergesort(lst[midpoint:]) # right = mergesort([7])
# ...
同样，递归停止，因为新的left和right子问题是单元素列表，它满足基本情况 -
right = mergesort([4,7])
def mergesort(lst): # lst = [4,7]
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # midpoint = 1
left = mergesort(lst[:midpoint]) # left = [4] <-
right = mergesort(lst[midpoint:]) # right = [7] <-
# ...
return newlist # newlist = [4,7]
最后最外层的mergesort电话可以返回——
mergesort([5,2,4,7])
def mergesort(lst): # lst = [5,2,4,7]
if len(lst) <= 1:
# ...
else:
midpoint = len(lst) // 2 # midpoint = 2
left = mergesort(lst[:midpoint]) # left = [2,5]
right = mergesort(lst[midpoint:]) # right = [4,7]
# ...
return newlist # newlist = [2,4,5,7]
# => [2,4,5,7]
综上所述，递归是一种函数式遗产，因此将其与函数式风格一起使用会产生最佳结果。这意味着避免突变、变量重新分配和其他副作用。考虑这个替代方案，它通过明确分离程序的关注点来降低概念开销 -
def mergesort(lst):
def split(lst):
m = len(lst) // 2
return (lst[:m], lst[m:])
def merge(l, r):
if not l:
return r
elif not r:
return l
elif l[0] < r[0]:
return [l[0]] + merge(l[1:], r)
else:
return [r[0]] + merge(l, r[1:])
if len(lst) <= 1:
return lst
else:
(left, right) = split(lst)
return merge(mergesort(left), mergesort(right))
mergesort([5,2,4,7])
# => [2,4,5,7]
你的问题的答案是：副本。
每个函数都是计算的配方。
调用函数时，将创建配方的副本。 每个调用都涉及创建单独的副本。 这就是每个都可以独立运行的方式，并且它们不会混在一起。
通常，递归函数调用没有什么特别之处。 函数调用就是函数调用，无论调用的函数是什么。 调用函数，执行其操作，其结果返回给调用方。 至于递归，你不应该跟踪它。 它自己做它的工作。 你应该向自己证明基本情况是正确的，并且递归大小写是正确的。仅此而已。
然后保证它以多么复杂的方式工作，它的全部意义在于我们不关心它是如何做到的，即它的确切步骤顺序。
所以特别是在你的情况下，假设mergesort确实正常工作(等等，什么？没关系，暂时暂停你的怀疑)，
left = mergesort(lst[:midpoint])
调用函数mergesortlst的前半部分，从它的开始到它的中点，并将结果 - 这是排序的前半部分，通过假设，- 存储在变量left中;
right = mergesort(lst[midpoint:])
调用函数mergesort与lst的后半部分，从它的中点到它的结束，并将结果 - 这是排序的后半部分，假设， - 存储在变量right中;
然后你需要说服自己，代码的其余部分从这两个排序的半部分创建newlist，以便newlist也按正确的顺序排序。
然后通过数学归纳原理证明了mergesort的正确性。
通过假设它有效，我们证明它确实有效！收获在哪里？没有陷阱，因为通过假设工作的两种情况是针对两个较小的输入(这就是我们的递归情况)。
当我们一遍又一遍地将一个东西分成两部分时，最终我们要么只剩下一个单例，要么留下一个空的东西。这两个自然是排序的(这是我们的基本情况)。
递归是信仰的飞跃。假设这个东西正在工作，然后你就可以使用它了。如果你正确地使用它，你将因此构建你最初使用的东西！