如果递归函数返回到开头，它如何运行？

Question

我是一个新手程序员

我正在研究一个使用递归函数的问题。虽然我可以理解要点，但有一个不清楚的问题，我无法在调试过程中立即破译。感谢您对我的问题的帮助。

这个问题的概念（合并排序）非常简单，但我对递归函数的一般工作方式感到困惑。下面是我正在处理的程序（来自佐治亚理工学院关于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]))

问题:当程序执行到这行时会发生什么< code > left = merge sort(lst[:midpoint])？

根据我的理解，它返回到程序的第一行，然后再次向下到达同一行（就像do一样）。

所以它一直在返回！然而，这使得程序对我来说不可读。一般来说，程序如何处理递归函数是我的主要问题。我不明白它是如何工作的。

Answer 1

你的问题的答案是：副本。

每个函数都是一个计算方法。

调用函数时，将创建配方的副本。每个调用都涉及创建一个单独的副本。这就是每个调用可以独立操作的方式，并且它们不会混在一起。

通常，递归函数调用没有什么特别之处。函数调用是函数调用，无论调用的函数是什么。调用函数，执行它所做的事情，并将其结果返回给调用方。至于递归，你不应该跟踪它。它自己做自己的工作。你应该向自己证明基本情况是正确的，递归情况是正确的。仅此而已。

然后，它保证以任何复杂的方式工作，而它的全部意义在于我们不必关心它到底是如何工作的，也就是说，它的确切步骤顺序。

所以特别是在你的情况下，假设mergesort确实工作正常（等等，什么？没关系，暂时停止你的怀疑），

        left = mergesort(lst[:midpoint])

调用函数 mergesort 与 lst 的前半部分，从它的开始到它的中点，并将结果 （这是按假设排序的前半部分） 存储在左边的变量中;然后

        right = mergesort(lst[midpoint:])

调用函数＜code＞mergesort＜/code＞以＜code＞lst＜/code＞的后半部分，从其中点到末端，并将结果（根据假设排序的后半段）存储在变量＜code＞right＜/code＞中；

然后，您需要说服自己，代码的其余部分将从这两个排序的部分创建＜code＞newlist＜/code＞以便＜code＞newlist＜/code＞也按正确的顺序排序。

然后通过数学归纳法的原理证明了< code>mergesort的正确性。

通过假设它有效，我们证明它确实有效！陷阱在哪里？这是没有问题的，因为根据假设工作的两种情况是针对两个较小的输入（这是我们的递归情况）。

当我们一遍又一遍地把一个东西分成两部分时，最终我们要么只剩下一个单例，要么留下一个空的东西。这两者是自然排序的（这是我们的基本情况）。

递归是信念的飞跃。假设这东西能用，你就可以使用它。如果你正确地使用它，你将会因此建造出你最初使用的东西！

Answer 2

当程序运行到这一行时会发生什么？根据我的理解，它返回到程序的第一行，然后再下来到达同一行...

每次程序递归时，它都会使用较小的列表调用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([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

左子问题的递归停止，并返回[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 = 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]

现在，对第一个< code >右子问题重复这些步骤

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])
        # ...

同样，递归停止，因为新的左和右子问题是一个单元素列表，它满足基本情况-

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]

最后，最外层的＜code＞mergesort＜/code＞调用可以返回-

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]