如果递归函数返回到开头，该如何操作？

debugcn 发表于 Dev

法哈德·塔玛塞比

我是新手程序员

我正在查找使用递归函数的问题。尽管我可以理解要点，但是有一个不清楚的问题，在调试过程中无法立即解密。感谢您在我的问题上的帮助。

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

例如，如果我们首先mergesort用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被称为with[5,2]和[4,7]sub-problems。让我们对第一个子问题重复这些步骤-

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