4.3　闭包和函数的递归调用

4.3.1　闭包

在Python中，闭包（Closure）指函数的嵌套。可以在函数内部定义一个嵌套函数，将嵌套函数视为一个对象，所以可以将嵌套函数作为定义它的函数的返回结果。

【例4-5】使用闭包的例子。

程序代码：

在函数func_lib（）中定义了一个嵌套函数add（x，y），并作为函数func_lib（）的返回值。

程序运行结果：

4.3.2　函数的递归调用

1.递归调用

函数在执行过程中直接或间接调用自己本身，称为递归调用。Python语言允许递归调用。

【例4-6】求1到5的平方和。

程序代码：

程序运行结果：

在调用f（）函数的过程中，又调用了f（）函数，这是直接调用本函数。

如果在调用f1（）函数过程中要调用f2（）函数，而在调用f2（）函数过程中又要调用f1（）函数，这是间接调用本函数，如图4-3所示。

从图4-3可以看到，递归调用都是无终止的调用自己。程序中不应该出现这种无止境的递归调用，而应该出现有限次数、有终止的递归调用。这可以使用if语句来控制，当满足某一条件时递归调用结束。例如，求1到5的平方和中递归调用结束的条件是x=1。

【例4-7】从键盘输入一个整数，求该数的阶乘。

根据求一个数n的阶乘的定义n！=n（n-1）！，可写成如下形式：

fac（n）=1　　（n=1）

fac（n）=n*fac（n-1）　　（n>1）

程序代码：

程序运行结果：

思考：根据递归的处理过程，若fac（）函数中没有语句if n==1：p=1，程序的运行结果将如何？

2.递归调用的执行过程

递归调用的执行过程分为递推过程和回归过程两部分。这两个过程由递归终止条件控制，即逐层递推，直至递归终止条件，然后逐层回归。递归调用同普通的函数调用一样利用了先进后出的栈结构来实现。每次调用时，在栈中分配内存单元保存返回地址以及参数和局部变量；而与普通函数调用不同的是，由于递推的过程是一个逐层调用的过程，因此存在一个逐层连续的参数入栈过程，调用过程每调用一次自身，把当前参数压栈，每次调用时都首先判断递归终止条件，直到达到递归终止条件为止；接着回归过程不断从栈中弹出当前的参数，直到栈空返回到初始调用处为止。

图4-4所示为例4-7的递归调用过。

注意：无论是直接递归还是间接递归都必须保证在有限次调用之后能够结束，即递归必须有结束条件，并且递归能向结束条件发展。例如，fac（）函数中的参数n在递归调用中每次减1，总可达到n==1的状态而结束。

函数递归调用解决的问题，也可用非递归函数实现，例如例4-7中，可用循环实现求n！。但在许多情形下如果不用递归方法，程序算法将十分复杂，很难编写。

下面的实例显示了递归设计技术的效果。

【例4-8】汉诺塔（Hanoi）问题。汉诺塔源自于古印度，是非常著名的智力趣题，在很多算法书籍和智力竞赛中都涉及。有A、B、C三根柱子（见图4-5），A柱上有n个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由A柱搬动到C柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。

编程求解汉诺塔问题并打印出搬动的步骤。

分析：

（1）A柱只有一个盘子的情况：A柱→C柱。

（2）A柱有两个盘子的情况：小盘A柱→B柱，大盘A柱→C柱，小盘B柱→C柱。

（3）A柱有n个盘子的情况：将此问题看成上面n-1个盘子和最下面第n个盘子的情况。n-1个盘子A柱→B柱，第n个盘子A柱→C柱，n-1个盘子B柱→C柱。问题转化成搬动n-1个盘子的问题，同样，将n-1个盘子看成上面n-2个盘子和下面第n-1个盘子的情况，进一步转化为搬动n-2个盘子的问题……依此类推，一直到最后成为搬动一个盘子的问题。

这是一个典型的递归问题，递归结束于只搬动一个盘子。

算法可以描述为：

（1）n-1个盘子A柱→B柱，借助于C柱。

（2）第n个盘子A柱→C柱。

（3）n-1个盘子B柱→C柱，借助于A柱。

其中，步骤（1）和步骤（3）继续递归下去，直至搬动一个盘子为止。由此，可以定义两个函数，一个是递归函数，命名为hanoi（n，source，temp，target），实现将n个盘子从源柱source借助中间柱temp搬到目标柱target；另一个命名为move（source，target），用来输出搬动一个盘子的提示信息。

程序代码：

程序运行结果：

注意：计算一个数的阶乘的问题可以利用递归函数和非递归函数解决，对于Hanoi塔问题，为其设计一个非递归程序却不是一件简单的事情。