# Python中的recursion基础

“写一个recursion函数，”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` `

` `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([])))))` `

` `>>> 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` `

` `>>> def listSum(ls, result): ... if not ls: ... return result ... return listSum(ls[1:], result + ls[0]) ... >>> listSum([1, 3, 4, 5, 6], 0) 19` `

` `>>> 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` `

` `>>> 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` `

` `>>> 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` `

recursion电源问题

` `power(2, 5) = 32 power(5, 2) = 25 power(3, 4) = 81` `

` `power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 power(5, 2) = 5 * 5 = 25 power(3, 4) = 3 * 3 * 3 * 3 = 81` `

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

` ` = 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` `

` `>>> 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` `

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

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