向上递归(Pass-Up Recursion)

先来看一下传统的递归

def sum(lst):"""把lst所有元素求和"""if len(lst) = 0:return 0return lst[0] + sum(lst[1:])

加入sum([1,2,3]),则是先求sum([2,3])；而要求sum([2,3]),则要求sum([3]), 求sum([3])则要求sum([]), sum([])=0；依次返回。
sum([3])=3 + 0 = 3
sum([2, 3]) = 2 + 3 = 5
sum([1,2,3]) = 1 + 5 = 6

可以看出，向下递推的过程并没有求值，向上回归的过程，逐步返回前一步的值给后一步才得出我们要的结果，这样的递归过程叫做向上递归(Pass-Up Recursion)。

向下递归(Pass-Down Recursion)

为了减小空间复杂度，我们可以回收利用不需要了的框架。所有需要的计算都直接在向下递归的过程中计算出来，直接返回最后一步的返回值即可。

def sum(lst, sumsofar):
"""sumsofar: 已经被加过的元素之和
"""if len (lst) == 0:return sumsofarsumsofar = sumsofar + lst[0]return sum(lst[1:], sumsofar)

注意

• 向下递归需要新增一个变量sumsofar，如果是寻找列表里最大的数，就需要有resultsofar，代表列表到前一个数的最大值。
• 向下递归需要一个辅助函数（helper function）。因为当用户使用上面这个函数时，还需要输入一个初始值，sum([1 2 3], 0)，这样就很不方便用户使用，我们可以使用辅助函数解决这个问题，而原来的函数的功能将会改为调用这个辅助函数即可。

def sum(lst):def sum_helper(lst, sumsofar):if len(lst) == 0:return sumsofarsumsofar += lst[0]return sum_helper(lst[1:], sumsofar)return sum_helper(lst, 0)		

练习

1.反转列表

def reverse(lst):""">>>reverse([1 2 3])[3 2 1]"""def reverse_helper(lst, reversed):if len(lst) == 0:return reversedreversed.insert(0,lst[0])return reverse_helper(lst[1:], reversed)return reverse_helper(lst,[])

2.幂运算

def power(x,n):""">>>power(2, 5)32"""def power_helper(result, k):"""k为幂的次数，等于n时完成计算"""if k == n:return resultresult *= xreturn power_helper(result,(k + 1))return power_helper(1,0)