如果 returns 到开头，递归函数如何运行？

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

问题：当程序到达这一行时会发生什么 left = mergesort( lst[:midpoint])？

根据我的理解，它 returns 到程序的第一行并再次向下到达同一行（就像 for 一样）。

所以它一直在回归！！！但是，这使程序对我来说不可读。一般来说，程序如何处理递归函数是我的主要问题。我无法理解它的工作方式。

Answer 1

What would happen When the program reaches this line left = mergesort(lst[:midpoint])? Based on my understanding, it returns to the first line of the program and comes down again to reach the same line...

每次程序重复出现时，它都会调用 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])
        # ...

So it keeps returning!!!

不完全是。当我们解决这一步中的子问题时，事情看起来就不一样了。当输入为一个元素或更少时，满足 base case 并且函数退出 -

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] 的答案是 returned。这同样适用于 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

接下来我们return我们的第一个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 调用可以 return -

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]

Answer 2

您问题的答案是：。

每个函数都是一个配方来计算。

当函数被调用时，配方的副本被创建。每次调用都涉及创建一个单独的副本。这就是每个人可以独立运作的方式，而且他们都而不是混杂在一起。

一般来说，递归函数调用没有什么特别之处。函数调用就是函数调用，不管被调用的函数是什么。一个函数被调用，做它做的事情，它的结果返回给调用者。至于递归，你不应该跟踪它。它自己完成工作。您应该向自己证明基本情况是正确的并且递归情况是正确的。就是这样。

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

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

        left = mergesort(lst[:midpoint])

用 lst 的前半部分调用函数 mergesort，从开始到中点，并存储结果 - 即 sorted上半年，假设，-在变量left中；然后

        right = mergesort(lst[midpoint:])

用 lst 的 second 一半调用函数 mergesort，从它的中点到它的末尾，并存储结果 - 这是 sorted 后半部分，by assumption, - in the variable right;

然后你需要说服自己，其余代码从这两个排序的一半创建 newlist，这样 newlist 就是也 按正确的顺序排序。

然后根据数学归纳法的原理证明了mergesort的正确性。

假设它有效，我们证明它确实有效！问题在哪里？没有问题，因为根据假设起作用的两种情况是针对两个 更小的 输入（这就是我们的 recursive 情况）。

当我们将一个东西分成两部分时，一遍又一遍，最终我们得到的不是一个单例，就是一个空的东西。这两个是自然排序的（这是我们的基本情况）。

递归是一种信仰的飞跃。假设这个东西在工作，那么你就可以使用它了。如果你正确地使用它，你就会构建出你最初使用的东西！

如果 returns 到开头，递归函数如何运行？

how can a recursive function operate if it returns to the beginning?

sorting

recursion

mergesort

function