Python中的recursion基础
“写一个recursion函数，”listSum“，它接受一个整数列表，并返回列表中所有整数的总和”。
例：
>>>> listSum([1,3,4,5,6]) 19 我知道如何做另一种方式，而不是recursion的方式。
def listSum(ls): i = 0 s = 0 while i < len(ls): s = s + ls[i] i = i + 1 print s
我需要基本的方法来做到这一点，因为特殊的内置函数是不允许的。
无论何时遇到这样的问题，都要用相同的函数表示函数的结果。
在你的情况下，你可以通过添加第一个数字来得到结果，其结果是调用与列表中其余元素相同的函数。
例如，
listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) = 1 + (3 + listSum([4, 5, 6])) = 1 + (3 + (4 + listSum([5, 6]))) = 1 + (3 + (4 + (5 + listSum([6])))) = 1 + (3 + (4 + (5 + (6 + listSum([])))))
现在， listSum([])应该是什么结果？ 它应该是0.这就是所谓的recursion的基本条件 。 当基本条件满足时，recursion将结束。 现在，让我们尝试实现它。
这里最主要的是分裂清单。 你可以使用切片来做到这一点。
简单的版本
>>> def listSum(ls): ... # Base condition ... if not ls: ... return 0 ... ... # First element + result of calling `listsum` with rest of the elements ... return ls[0] + listSum(ls[1:]) >>> >>> listSum([1, 3, 4, 5, 6]) 19
尾巴呼叫recursion
一旦你理解了上述recursion的工作方式，你可以尝试使它更好一点。 现在，要find实际的结果，我们也取决于前一个函数的值。 return语句不能立即返回值直到recursion调用返回结果。 我们可以通过将电stream传递给函数参数来避免这种情况，就像这样
>>> def listSum(ls, result): ... if not ls: ... return result ... return listSum(ls[1:], result + ls[0]) ... >>> listSum([1, 3, 4, 5, 6], 0) 19
在这里，我们将总和的初始值传递给参数listSum([1, 3, 4, 5, 6], 0) 。 然后，当基本条件满足时，我们实际上是在result参数中累加和，所以我们返回它。 现在，最后一个return语句有listSum(ls[1:], result + ls[0]) ，我们将第一个元素添加到当前result ，并再次传递给recursion调用。
这可能是了解尾巴呼叫的好时机。 它不会与Python相关，因为它不会执行尾部调用优化。
绕过索引版本
现在，您可能会认为我们正在创build如此多的中间列表。 我能避免吗？
当然可以。 您只需要下一个要处理的项目的索引。 但现在，基本情况会有所不同。 既然我们要通过索引，我们将如何确定整个列表是如何处理的？ 那么，如果索引等于列表的长度，那么我们已经处理了它的所有元素。
>>> def listSum(ls, index, result): ... # Base condition ... if index == len(ls): ... return result ... ... # Call with next index and add the current element to result ... return listSum(ls, index + 1, result + ls[index]) ... >>> listSum([1, 3, 4, 5, 6], 0, 0) 19
内部function版本
如果您现在查看函数定义，则将三个parameter passing给它。 比方说，你要释放这个函数作为一个API。 当用户实际find列表的总和时，传递三个值是否方便？
不。 我们能做些什么呢？ 我们可以创build另一个函数，这个函数对于实际的listSum函数是本地的，我们可以把所有的实现相关的parameter passing给它，像这样
>>> def listSum(ls): ... ... def recursion(index, result): ... if index == len(ls): ... return result ... return recursion(index + 1, result + ls[index]) ... ... return recursion(0, 0) ... >>> listSum([1, 3, 4, 5, 6]) 19
现在，当调用listSum时，它只是返回recursion内部函数的返回值，它接受index和result参数。 现在我们只传递这些值，而不是listSum的用户。 他们只需要通过列表进行处理。
在这种情况下，如果你观察参数，我们不会传递ls来recursion但我们正在使用它。 因为closures属性， ls在recursion内部是可访问的。
默认参数版本
现在，如果你想保持简单，没有创build一个内部函数，你可以使用默认的参数，像这样
>>> def listSum(ls, index=0, result=0): ... # Base condition ... if index == len(ls): ... return result ... ... # Call with next index and add the current element to result ... return listSum(ls, index + 1, result + ls[index]) ... >>> listSum([1, 3, 4, 5, 6]) 19
现在，如果调用者没有显式传递任何值，那么0将被分配给index和result 。
recursion电源问题
现在，让我们将这些想法应用于不同的问题。 例如，让我们尝试实现power(base, exponent)function。 它会返回base值的上升到权力exponent 。
power(2, 5) = 32 power(5, 2) = 25 power(3, 4) = 81
现在，我们怎样才能recursion呢？ 让我们试着了解如何实现这些结果。
power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 power(5, 2) = 5 * 5 = 25 power(3, 4) = 3 * 3 * 3 * 3 = 81
嗯，所以我们明白了。 base乘以自己， exponent次给出结果。 好的，我们如何处理呢？ 让我们尝试使用相同的函数来定义解决scheme。
power(2, 5) = 2 * power(2, 4) = 2 * (2 * power(2, 3)) = 2 * (2 * (2 * power(2, 2))) = 2 * (2 * (2 * (2 * power(2, 1))))
如果什么东西上了权力1，结果应该是什么？ 结果将是相同的数字，对不对？ 我们得到了我们recursion的基础条件:-)
= 2 * (2 * (2 * (2 * 2))) = 2 * (2 * (2 * 4)) = 2 * (2 * 8) = 2 * 16 = 32
好的，让我们来实现它。
>>> def power(base, exponent): ... # Base condition, if `exponent` is lesser than or equal to 1, return `base` ... if exponent <= 1: ... return base ... ... return base * power(base, exponent - 1) ... >>> power(2, 5) 32 >>> power(5, 2) 25 >>> power(3, 4) 81
好吧，如何定义尾调用优化版本呢？ 让我们将当前结果作为parameter passing给函数本身，并在满足基本条件时返回结果。 让我们保持简单，直接使用默认参数方法。
>>> def power(base, exponent, result=1): ... # Since we start with `1`, base condition would be exponent reaching 0 ... if exponent <= 0: ... return result ... ... return power(base, exponent - 1, result * base) ... >>> power(2, 5) 32 >>> power(5, 2) 25 >>> power(3, 4) 81
现在，我们在每个recursion调用中减lessexponent值，用base减less多个result ，并将其传递给recursion调用。 我们从价值1开始，因为我们正在接近这个问题。 recursion会像这样发生
power(2, 5, 1) = power(2, 4, 1 * 2) = power(2, 4, 2) = power(2, 3, 2 * 2) = power(2, 3, 4) = power(2, 2, 4 * 2) = power(2, 2, 8) = power(2, 1, 8 * 2) = power(2, 1, 16) = power(2, 0, 16 * 2) = power(2, 0, 32)
由于exponent变为零，基本条件得到满足， result将被返回，所以我们得到32 🙂
提前退出对于recursion函数是典型的。 seq在空时是虚的（因此当没有剩余的数字时）。
Slice语法允许将序列传递给recursion调用的函数，而不在当前步骤中消耗整数。
def listSum(seq): if not seq: return 0 return seq[0] + listSum(seq[1:]) print listSum([1,3,4,5,6]) # prints 19
def listSum(L): """Returns a sum of integers for a list containing integers. input: list of integers output: listSum returns a sum of all the integers in L. """ if L == []: return [] if len(L) == 1: return L[0] else: return L[0] + listSum(L[1:]) print listSum([1, 3, 4, 5, 6]) print listSum([]) print listSum([8])
