4.16　递归

现在，编写一个程序来完成一个常用的数学计算—计算正整数n的阶乘，写作n!。其计算公式如下：

n · (n - 1) · (n - 2)· … · 1

例如，5!为5·4·3·2·1，其值为120。其中，1!的值为1，0!的值被定义为1。

迭代因子方法

可以使用for语句通过迭代来计算5!，如下：

递归问题求解

递归问题的解决方法有几个共同点。当调用递归函数来求解问题时，它实际上只能对最简单的问题或基本问题进行求解。如果使用基本问题调用该函数，可以立即返回结果。如果使用更复杂的问题调用该函数，它通常会将问题分解为两部分—一部分函数知道如何操作，而另一部分则不知道。为了使递归可行，后一部分必须是与原始问题相同但更简单或更小的版本。因为这个新问题与原始问题相同，所以函数可以通过调用自身的新副本来处理规模较小的相同问题，这种调用方式称为递归调用，也称为递归步骤。将问题分成两个较小的部分分别求解的思想是本书前面介绍过的分治法的一种表现形式。

在执行递归调用的同时，其原始函数调用仍处于活动的状态（即它尚未完成执行）。它还会产生更多的递归调用，因为函数会将每个新的子问题都分解成两个部分。为了使递归最终能够终止，函数每次都要使用原始问题的更简单版本调用自身，而逐渐变小的问题构成的序列必须收敛于基本问题。当函数识别到基本问题时，它会将结果返回到它的上一个副本。递归会依序进行一系列的返回，直到最初的函数调用将最终结果返回给调用者。

递归求阶乘

通过观察，我们可以将n!写成如下的递归形式：

n! = n · (n - 1)!

例如，5!等于5·4!，如下：

5! = 5·4·3·2·1

5! = 5·(4·3·2·1)

5! = 5·(4!)

递归可视化

计算5!的进程如下图所示。左图显示递归调用持续进行，直到计算出1!（基本问题）的值为1，终止递归。右图从下到上依序显示每次从递归调用返回到其调用者的值，直到计算出最终值并返回。

实现递归求阶乘函数

下面的代码使用递归来计算并显示整数0～10的阶乘：

代码段[4]的递归函数factorial首先确定终止条件number<=1是否为True。如果此条件为True（基本问题），则factorial返回1并且不需要进一步递归。如果number大于1，则第二个return语句将问题表示为number和递归调用factorial(number-1)的乘积。后者是一个比原始计算（factorial(number)）稍小的问题。请注意，函数factorial接收的参数必须是非负的，但是本例没有对这种情况进行测试。

代码段[5]中的循环调用从0到10的factorial函数，输出的结果显示出阶乘在快速增长。与许多其他编程语言不同，Python不限制整数的大小。

间接递归

递归函数可以调用另一个函数，该函数又可以回调递归函数，称为间接递归调用或间接递归。例如，函数A调用函数B，函数B又调用函数A。这种调用方式也是递归，因为函数A的第二次调用发生在对函数A的第一次调用还处于活动状态时。也就是说，对函数A的第一次调用尚未完成执行（因为它正在等待函数B将结果返回给它）并且还没有返回到函数A的原始调用者。

堆栈溢出和无限递归

计算机中的内存量是有限的，因此只能使用一定量的内存将活动记录存储在函数调用堆栈内。如果递归函数的调用次数超过了堆栈中活动记录的存储上限，则会发生称为堆栈溢出的致命错误。这通常是由无限递归导致的。出现无限递归的原因可能是遗漏了基本问题或错误地写入递归步骤而导致无法收敛到基本问题。这个错误类似于迭代（非递归）解决方案中的无限循环问题。