本章目标

• 理解很多复杂问题，如果不用递归就很难解决，用递归也许非常简单
• 学会怎样进行递归编程
• 理解并应用递归三定律
• 理解递归也是一种迭代
• 建立一个问题的递归方法
• 理解递归在计算机系统内是如何进行的。

什么是递归？

递归是解决问题的一种方法，它把问题拆解得越来越小，直到变得非常容易，一般情况下，递归过程要包括一个自我访问的函数。与表面看起来似乎不一样，其实递归允许我们写出非常简洁的代码，但解决问题却很复杂，用其他办法很难处理。

列表元素求和

我们先不用递归，看一个问题不用递归是如何处理的。

假如你想计算一个整数列表各项的和，如[1,3,5,7,9]。下面的代码所示，函数使用了一个累加变量（theSum）来计算所有列表的项目的和：

deflistsum(numList):

    theSum = 0

    for i in numList:

        theSum = theSum + i

    return theSum

 

print(listsum([1,3,5,7,9]))

假如我们没有while和for循环语句，你又怎样来计算一系列数字的和呢？如果你是数学家，也许会想到，加法是一个函数，有两个参数，就是一对数字。把一个列表求和问题转为两个数字的求和问题，那么上面的过程可以写成一个完全括号表达式：

((((1+3)+5)+7)+9)

We can also parenthesize the expression theother way around,

还可以用另一种完全括号表达式：

(1+(3+(5+(7+9))))

注意最里层的括号，（7+9）的计算，我们不需要循环或其他结构就能算出来，事实上用下面的顺序计算出最后的和：

 

total= (1+(3+(5+(7+9)))) total= (1+(3+(5+16))) total= (1+(3+21)) total= (1+24) total= 25

这种想法怎样变成python程序呢？首先要重新表达一下元素求和的问题。我们也可以说列表元素之和，是第一个元素numList[0]和其他所有元素的和numList[1:]，就如下式所示：

 

listSum(numList)=first(numList)+listSum(rest(numList))

在这个等式中，first(numList) 是列表第一个数据项，而rest(numList)是除第一项之外所有其他项，用python这样表达：

1	ef listsum(numList):    if len(numList) == 1:         return numList[0]    else:         return numList[0] + listsum(numList[1:])   print(listsum([1,3,5,7,9]))
2
3
4
5
6
7

这段7行的代码里有几个关键的想法。首先，第2行，检查这个列表是否只有一个数据，这步检查很重要，是函数的“例外条款”。长度为1的列表求得最简单，就是数据自身。其次，第5行，我们的函数调用了它自己！这正是我们把它叫做递归算法的原因，递归函数就是调用自己的函数。

如图1所示，一连串的递归调用来求得列表[1,3,5,7,9]的和，应该把这连串的调用当作连续的简化，每次调用，都是解决越来越简单的问题，直到问题再也不能简化。

图1 列表求和的递归调用

当问题到了不能再简化的终点，我们开始归拢被简化的问题，直到最开始的问题得以解决。如图2所示，列表求和从连串调用中返回，当listSum从最早一次调用中返回时，整个问题就解决了。

图2 列表求和的连续返回过程

递归三定律