如果递归函数返回到开头，该如何操作? [英] how can a recursive function operate if it returns to the beginning?
问题描述
我是程序员新手
我正在查找使用递归函数的问题.尽管我可以理解要点，但是有一个不清楚的问题，在调试过程中无法立即解密.感谢您在我的问题上的帮助.
I am looking up into a problem which is using a recursive function. Though I could understand the main point, there is an unclear issue which I could not decipher immediately as I go through the debugging process. I will appreciate your help on my question.
问题的概念(合并排序)非常简单，但是我对递归函数的一般工作方式感到困惑.贝娄是我正在处理的程序(来自Python的佐治亚理工学院课程):
The problem's concept (merge sorting) is pretty straight forward, but I am confused with the way a recursive function works in general. Bellow is the program I am dealing with (from Georgia Tech course on 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])时会发生什么?
QUESTION: What happens when the program reaches this line left = mergesort( lst[:midpoint])?
根据我的理解，它返回到程序的第一行，然后再次下降到同一行(就像 for 所做的那样).
Based on my understanding, it returns to the first line of the program and comes down again to reach the same line (just like for does).
所以它一直在返回！！！但是，这使程序对我来说不可读.总的来说，程序如何处理递归函数是我的主要问题.我不明白它的工作方式.
So it keeps returning!!! This, however, makes the program unreadable to me. In general, How the program deals with the recursive function is my main question. I could not understand the way it works.
推荐答案
当程序到达此行
left = mergesort(lst [:midpoint])时会发生什么?根据我的理解，它返回到程序的第一行，然后再次下降到同一行...
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...
程序每次重复执行时，都会调用带有 smaller 列表的 mergesort .我们称其为子问题".-
Each time the program recurs, it calls mergesort with a smaller list. We call this a "sub-problem" -
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 -
For example, if we first call mergesort with a 4-element list -
mergesort([5,2,4,7])
输入列表 lst 不满足基本情况，因此我们进入 else 分支-
The input list, lst, does not meet the base case, so we move onto the else branch -
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] 子问题调用的.让我们对第一个子问题重复这些步骤-
Notice mergesort is called with [5,2] and [4,7] sub-problems. Let's repeat these steps for the first sub-problem -
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!!!
不完全是.当我们在此步骤中解决子问题时，情况似乎有所不同.当输入为一个或更少的元素时，满足基本情况且函数退出-
Not exactly. When we solve the sub-problems in this step, things looks different. When the input is one element or less, the base case is satisfied and the function exits -
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 子问题-
Recursion stops for the left sub-problem and the answer of [5] is returned. The same applies for the right sub-problem -
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 子问题-
Next we return our first left sub-problem -
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 子问题重复这些步骤-
You would now repeat these steps for the first right sub-problem -
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 子问题是单元素列表，因此递归停止，该列表满足基本情况-
Again, recursion stops as the new left and right sub-problems are a single-element list, which satisfies the base case -
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 调用可以返回-
And finally the outermost mergesort call can 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]
所有这些都说明，递归是一种功能性遗产，因此将其与功能性样式一起使用可产生最佳效果.这意味着避免诸如突变，变量重新分配和其他副作用之类的事情.考虑这种替代方案，它可以通过明确区分程序的关注点来降低概念上的开销-
All of that said, recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutations, variable reassignments, and other side effects. Consider this alternative which lowers the conceptual overhead by clearly separating the program's concerns -
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]
这篇关于如果递归函数返回到开头，该如何操作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
