5.3　递归调用

所谓递归调用，是指函数内部再次调用当前函数的过程。过去有些语言无法实现递归调用，现在几乎所有语言都支持这一编程技术。

嵌套结构体的高效处理

递归调用是不可或缺的吗？不，当然不是。使用了递归调用的程序，也可以不用递归调用来实现 10。

10最坏情况下，自己来设计栈也是可以实现的。比如把使用了递归调用的汉诺塔求解过程用不带递归调用的方式实现。这就是一个不错的练习。

那么，递归调用这种程序设计技巧为什么会产生并一直被使用呢？这是因为，对于某些类型的操作，使用递归调用可以使程序编写变得轻松很多。这里指的是那些执行某些步骤中途又针对不同对象（参数）执行相同步骤的情况，即嵌套结构体的情况。处理嵌套的数据结构时，代码通常也会变成嵌套结构。

嵌套结构体的处理方法

在物理实体的制造中，要说某零部件是使用该零部件自己制造出来的，这是极其难以想象的一件事。初学程序设计时，很多人对递归调用感到困惑。作为处理嵌套结构的一个例子，我们来看一下为嵌套列表的全部元素求和的问题 11。

11顺便一提，笔者认为使用阶乘计算和裴波那契数列计算这两个例子来讲解递归调用恐有不妥。这是因为，这两个计算不需要递归调用，使用普通的循环体就可以实现，并且对于裴波那契数列计算如果简单地使用递归，其性能比使用循环体要差很多。

比如，[1,2,[3,4],5] 这样一个列表，可以看作是将 [3,4] 这个列表嵌套放入 [1,2,?,5] 这个列表产生的。要为这样一个嵌套结构的列表里所有元素求和，该如何实现呢？

下面的 Python 代码使用 for 语句把列表中的元素逐个取出，如果为整数则做相加运算，执行情况如下。12

12在 Python 语言中不存在 is_integer 这个函数，实际起相同作用的是 isinstance(x, int) 函数。因为这个无关正题，在这里我们选择使用一个名字更好理解的函数。

Python
def total(xs):
result = 0
for x in xs:
# 逐个取出列表xs中的元素放进x
if is_integer(x):
# 如果x为整数则做加法
result += x
else:
# 如果x不为整数该如何处理？？

return result

最早出来的是 1 和 2，因为它们都是整数，所以与 result 做加法，最后结果是 3。到此为止都很顺利，但接下来出现的 [3,4] 不是整数了，这个该如何处理呢？

无法用 for 语句实现

也许有人说，因为这是一个列表，在 for 语句结构中对其元素做特别加法不就行了。对于这个例子中的输入数据，这种实现方法恰巧是可行的。对于最多仅有两重嵌套的输入数据，只要用二重 for 语句就可以处理。但是，输入为三重嵌套结构的列表又会怎样呢？此时第二个 for 语句的处理中又碰到一个列表，对这个列表该怎么处理呢？

Python
def total(xs):
result = 0
for x in xs:
if is_integer(x):
result += x
else:
# x为列表，所以用for语句处理
for y in x:
if is_integer(y):
result += y
else:
# 再来一个列表时该如何处理呢？

return result

此处即使再追加一个 for 语句，这段程序也只是针对三重嵌套结构的处理管用，如果数据有四重、五重嵌套就无法处理了。

这种多重嵌套的数据结构并不罕见，比如 HTML 语言中的标签就有几十层嵌套。处理这样的数据结构，需要的是不管多少层嵌套都能做处理的机制，多次嵌套 for 语句是无法做到的。

使用递归调用

于是就有了递归调用。这种方法在实现对嵌套列表元素求和的函数 total 中，又调用该函数自身，如同该函数已经实现完成了一样。

Python
def total(xs):
result = 0
for x in xs:
if is_integer(x):
result += x
else:
# x为嵌套列表，所以用total求里面的元素的总和！
result += total(x)

return result

这样就完成了。不管对函数 total 传递几重嵌套结构体的列表，都能把它里面的元素的和求出来。

递归调用执行时的程序流

给函数 total 传递参数 [1, [2, 3], 4] 并调用会发生什么呢？我们顺着递归调用的执行过程一起来看一下。

首先，函数 total 带有参数 [1, [2, 3], 4] 被调用时，xs 为 [1, [2, 3], 4]，result 为 0（图 5.4）。

图 5.4　循环开始前

然后开始执行 for 语句循环。先把 xs 的第一个元素取出，为整数的 1，故执行 result 加 1，result 由 0 变成 1（图 5.513）。

13此图为简化图形，未把 x 放入其中。

图 5.5　对 1 的操作

然后循环至下一个元素。把 xs 的第二个元素取出，发现是非整数的 [2, 3]。为了求解这个数组的和，把 [2, 3] 作为参数调用函数 total。在第二个调用中，xs 为 [2, 3]，result 为 0（图 5.6）。

图 5.6　[2, 3] 非整数故递归调用 total

第二个调用中的 for 语句开始执行。把 xs 的第一个元素取出，为整数的 2，故执行 result 加 2，result 由 0 变成 2（图 5.7）。

图 5.7　处理 [2, 3] 中的 2

第二个调用中的 for 语句继续执行。把 xs 的第二个元素取出，为整数的 3，故执行 result 加 3，result 由 2 变成 5（图 5.8）。

图 5.8　处理 [2, 3] 中的 3

这样第二个调用中的 for 语句循环结束。循环体外有 return result，把此时 result 的值 5 返回函数调用的地方。在函数调用处，返回值与 result 相加，result 由 1 变成 6（图 5.9）。

图 5.9　返回 5 后对 1, [2, 3] 的处理结束

把 xs 的第三个元素取出，为整数的 4，故执行 result 加 4，result 由 6 变成 10（图 5.10）。

图 5.10　处理最后的 4

total 的第一次调用中的 for 语句执行完毕，result 值为 10，故将 10 返回至函数调用的地方。

这样就成功地返回了正确的结果。在这个执行过程中，针对每次函数调用都有单独的地方用来存储 xs 和 result 的值，并且在第二个 total 执行结束时第一个 total 能紧接着执行，这两点值得注意 14。

14在这个例子中，每次函数调用时都有各自的 result 值，这是因为 result 是函数的局部变量，在此不做深入说明。全局变量和局部变量的区别我们将在第 7 章详细论述。