Python中递归的基础知识

Question

Python中递归的基础知识

“编写一个递归函数，”listSum“，它获取整数列表并返回列表中所有整数的总和”。

例：

>>>> listSum([1,3,4,5,6])19

我知道如何以另一种方式做到这一点，但不是以递归的方式。

def listSum(ls):
    i = 0
    s = 0
    while i < len(ls):
        s = s + ls[i]
        i = i + 1
    print s

我需要基本的方法来执行此操作，因为不允许使用特殊的内置函数。

Answer 1

每当遇到这样的问题时，尝试用相同的函数表示函数的结果。在您的情况下，您可以通过添加第一个数字来获得结果，其结果是使用列表中的其余元素调用相同的函数。例如，listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6])&nbsp;=&nbsp;1&nbsp;+&nbsp;listSum([3,&nbsp;4,&nbsp;5,&nbsp;6]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;1&nbsp;+&nbsp;(3&nbsp;+&nbsp;listSum([4,&nbsp;5,&nbsp;6])) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;1&nbsp;+&nbsp;(3&nbsp;+&nbsp;(4&nbsp;+&nbsp;listSum([5,&nbsp;6]))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;1&nbsp;+&nbsp;(3&nbsp;+&nbsp;(4&nbsp;+&nbsp;(5&nbsp;+&nbsp;listSum([6])))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;1&nbsp;+&nbsp;(3&nbsp;+&nbsp;(4&nbsp;+&nbsp;(5&nbsp;+&nbsp;(6&nbsp;+&nbsp;listSum([])))))现在，应该是什么结果listSum([])？它应该是0.这被称为递归的基本条件。当满足基本条件时，递归将结束。现在，让我们尝试实现它。这里的主要内容是拆分列表。你可以使用切片来做到这一点。简单版>>>&nbsp;def&nbsp;listSum(ls):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Base&nbsp;condition...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;not&nbsp;ls:...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;First&nbsp;element&nbsp;+&nbsp;result&nbsp;of&nbsp;calling&nbsp;`listsum`&nbsp;with&nbsp;rest&nbsp;of&nbsp;the&nbsp;elements...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ls[0]&nbsp;+&nbsp;listSum(ls[1:])>>>&nbsp;>>>&nbsp;listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6])19尾调用递归一旦你理解了上面的递归是如何工作的，你可以试着让它更好一点。现在，为了找到实际结果，我们也依赖于前一个函数的值。return在递归调用返回结果之前，该语句不能立即返回该值。我们可以避免这种情况，将当前传递给函数参数，就像这样>>>&nbsp;def&nbsp;listSum(ls,&nbsp;result):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;not&nbsp;ls:...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;listSum(ls[1:],&nbsp;result&nbsp;+&nbsp;ls[0])...&nbsp;>>>&nbsp;listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6],&nbsp;0)19在这里，我们将总和的初始值传递给参数，该参数为零listSum([1, 3, 4, 5, 6], 0)。然后，当满足基本条件时，我们实际上在result参数中累加和，所以我们返回它。现在，最后一个return语句有listSum(ls[1:], result + ls[0])，我们将第一个元素添加到当前result并将其再次传递给递归调用。这可能是了解Tail Call的好时机。它与Python无关，因为它不执行Tail调用优化。传递索引版本现在，您可能认为我们正在创建这么多中间列表。我可以避免吗？当然可以。您只需要接下来要处理的项目的索引。但现在，基本情况将有所不同。由于我们将要传递索引，我们如何确定整个列表的处理方式？好吧，如果索引等于列表的长度，那么我们已经处理了它中的所有元素。>>>&nbsp;def&nbsp;listSum(ls,&nbsp;index,&nbsp;result):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Base&nbsp;condition...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;index&nbsp;==&nbsp;len(ls):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Call&nbsp;with&nbsp;next&nbsp;index&nbsp;and&nbsp;add&nbsp;the&nbsp;current&nbsp;element&nbsp;to&nbsp;result...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;listSum(ls,&nbsp;index&nbsp;+&nbsp;1,&nbsp;result&nbsp;+&nbsp;ls[index])...&nbsp;>>>&nbsp;listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6],&nbsp;0,&nbsp;0)19内功能版如果现在查看函数定义，则将三个参数传递给它。假设您要将此功能作为API发布。当用户实际找到列表的总和时，是否可以方便地传递三个值？不。我们对于它可以做些什么呢？我们可以创建另一个函数，它是实际listSum函数的本地函数，我们可以将所有与实现相关的参数传递给它，就像这样>>>&nbsp;def&nbsp;listSum(ls):......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def&nbsp;recursion(index,&nbsp;result):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;index&nbsp;==&nbsp;len(ls):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;recursion(index&nbsp;+&nbsp;1,&nbsp;result&nbsp;+&nbsp;ls[index])......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;recursion(0,&nbsp;0)...&nbsp;>>>&nbsp;listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6])19现在，当listSum调用它时，它只返回recursion内部函数的返回值，它接受index和result参数。现在我们只传递这些值，而不是用户listSum。他们只需要传递要处理的列表。在这种情况下，如果您观察参数，我们不会传递ls给recursion我们，但我们在其中使用它。由于封闭属性，ls内部可访问recursion。默认参数版本现在，如果你想保持简单，不创建内部函数，你可以使用默认参数，就像这样>>>&nbsp;def&nbsp;listSum(ls,&nbsp;index=0,&nbsp;result=0):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Base&nbsp;condition...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;index&nbsp;==&nbsp;len(ls):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Call&nbsp;with&nbsp;next&nbsp;index&nbsp;and&nbsp;add&nbsp;the&nbsp;current&nbsp;element&nbsp;to&nbsp;result...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;listSum(ls,&nbsp;index&nbsp;+&nbsp;1,&nbsp;result&nbsp;+&nbsp;ls[index])...&nbsp;>>>&nbsp;listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6])19现在，如果调用者没有显式传递任何值，那么0将分配给index和result。递归电源问题现在，让我们将想法应用于另一个问题。例如，让我们尝试实现该power(base, exponent)功能。它会将base提升的价值归还给权力exponent。power(2,&nbsp;5)&nbsp;=&nbsp;32power(5,&nbsp;2)&nbsp;=&nbsp;25power(3,&nbsp;4)&nbsp;=&nbsp;81现在，我们如何递归地做到这一点？让我们试着了解这些结果是如何实现的。power(2,&nbsp;5)&nbsp;=&nbsp;2&nbsp;*&nbsp;2&nbsp;*&nbsp;2&nbsp;*&nbsp;2&nbsp;*&nbsp;2&nbsp;=&nbsp;32power(5,&nbsp;2)&nbsp;=&nbsp;5&nbsp;*&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;25power(3,&nbsp;4)&nbsp;=&nbsp;3&nbsp;*&nbsp;3&nbsp;*&nbsp;3&nbsp;*&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;81嗯，所以我们明白了。该base相乘本身，exponent时间给出结果。好的，我们如何处理它。让我们尝试使用相同的功能定义解决方案。power(2,&nbsp;5)&nbsp;=&nbsp;2&nbsp;*&nbsp;power(2,&nbsp;4) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;(2&nbsp;*&nbsp;power(2,&nbsp;3)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;(2&nbsp;*&nbsp;(2&nbsp;*&nbsp;power(2,&nbsp;2))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;(2&nbsp;*&nbsp;(2&nbsp;*&nbsp;(2&nbsp;*&nbsp;power(2,&nbsp;1))))如果有什么东西被提升到1？结果将是相同的数字，对吗？我们得到了递归的基本条件:-)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;(2&nbsp;*&nbsp;(2&nbsp;*&nbsp;(2&nbsp;*&nbsp;2))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;(2&nbsp;*&nbsp;(2&nbsp;*&nbsp;4)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;(2&nbsp;*&nbsp;8) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;2&nbsp;*&nbsp;16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;32好吧，让我们实现它。>>>&nbsp;def&nbsp;power(base,&nbsp;exponent):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Base&nbsp;condition,&nbsp;if&nbsp;`exponent`&nbsp;is&nbsp;lesser&nbsp;than&nbsp;or&nbsp;equal&nbsp;to&nbsp;1,&nbsp;return&nbsp;`base`...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;exponent&nbsp;<=&nbsp;1:...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;base......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;base&nbsp;*&nbsp;power(base,&nbsp;exponent&nbsp;-&nbsp;1)...&nbsp;>>>&nbsp;power(2,&nbsp;5)32>>>&nbsp;power(5,&nbsp;2)25>>>&nbsp;power(3,&nbsp;4)81好的，如何定义Tail调用优化版本呢？让我们将当前结果作为参数传递给函数本身，并在满足基本条件时返回结果。让我们保持简单并直接使用默认参数方法。>>>&nbsp;def&nbsp;power(base,&nbsp;exponent,&nbsp;result=1):...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Since&nbsp;we&nbsp;start&nbsp;with&nbsp;`1`,&nbsp;base&nbsp;condition&nbsp;would&nbsp;be&nbsp;exponent&nbsp;reaching&nbsp;0...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;exponent&nbsp;<=&nbsp;0:...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;power(base,&nbsp;exponent&nbsp;-&nbsp;1,&nbsp;result&nbsp;*&nbsp;base)...&nbsp;>>>&nbsp;power(2,&nbsp;5)32>>>&nbsp;power(5,&nbsp;2)25>>>&nbsp;power(3,&nbsp;4)81现在，我们减少exponent每个递归调用和多个resultwith&nbsp;的值，base并将其传递给递归power调用。我们从价值开始1，因为我们正在反过来解决问题。递归会像这样发生power(2,&nbsp;5,&nbsp;1)&nbsp;=&nbsp;power(2,&nbsp;4,&nbsp;1&nbsp;*&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;4,&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;3,&nbsp;2&nbsp;*&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;3,&nbsp;4) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;2,&nbsp;4&nbsp;*&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;2,&nbsp;8) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;1,&nbsp;8&nbsp;*&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;1,&nbsp;16) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;0,&nbsp;16&nbsp;*&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;power(2,&nbsp;0,&nbsp;32)由于exponent变为零，基本条件得到满足并且result将返回，因此我们得到32:-)

Answer 2

提前退出是典型的递归函数。seq空的时候是虚假的（因此当没有数字可用时）。切片语法允许将序列传递给递归调用的函数，而不会在当前步骤中消耗整数。def&nbsp;listSum(seq): &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;not&nbsp;seq: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0 &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;seq[0]&nbsp;+&nbsp;listSum(seq[1:])print&nbsp;listSum([1,3,4,5,6])&nbsp;&nbsp;#&nbsp;prints&nbsp;19

Answer 3

另一个版本：def&nbsp;listSum(ls): &nbsp;&nbsp;&nbsp;&nbsp;ls_len&nbsp;=&nbsp;len(ls) &nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Base&nbsp;condition &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;ls_len==1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ls[0] &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;ls_len==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;None &nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;ls&nbsp;=&nbsp;listSum(ls[0:i])&nbsp;+&nbsp;listSum(ls[i:]) &nbsp;&nbsp;&nbsp;&nbsp;elif&nbsp;ls_len%2==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;int(ls_len/2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;listSum(ls[0:i])&nbsp;+&nbsp;listSum(ls[i:]) &nbsp;&nbsp;&nbsp;&nbsp;else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;int((ls_len-1)/2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;listSum(ls[0:i])&nbsp;+&nbsp;listSum(ls[i:])关注@ thefourtheye的例子，我们可以说：listSum([1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;6])&nbsp;=&nbsp;listSum([1,&nbsp;3])&nbsp;+&nbsp;listSum([4,&nbsp;5,&nbsp;6]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;(listSum([1])&nbsp;+&nbsp;listSum([3]))&nbsp;+&nbsp;(listSum([4])&nbsp;+&nbsp;listSum([5,&nbsp;6])) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;(listSum([1])&nbsp;+&nbsp;listSum([3]))&nbsp;+&nbsp;(listSum([4])&nbsp;+&nbsp;(listSum([5])&nbsp;+&nbsp;listSum([6])))基本条件：当ls只有一个元素时，返回该值。