Python基础教程 两个经典案例：阶乘和幂

6.6.1 两个经典案例：阶乘和幂

本节探讨两个经典的递归函数。首先，假设你要计算数字n的阶乘。 n的阶乘为n × (n1) × (n 2) × … × 1，在数学领域的用途非常广泛。例如，计算将n个人排成一队有多少种方式。如何计算阶乘呢？可使用循环。

def factorial(n):

result = n

for i in range(1, n):

result *= i

return result

这种实现可行，而且直截了当。大致而言，它是这样做的：首先将result设置为n，再将其依次乘以1到n1的每个数字，最后返回result。但如果你愿意，可采取不同的做法。关键在于阶乘的数学定义，可表述如下。

 1的阶乘为1。

 对于大于1的数字n，其阶乘为n1的阶乘再乘以n。

如你所见，这个定义与本节开头的定义完全等价。

下面来考虑如何使用函数来实现这个定义。理解这个定义后，实现起来其实非常简单。

def factorial(n):

if n == 1:

return 1

else:

return n * factorial(n - 1)

这是前述定义的直接实现，只是别忘了函数调用factorial(n)和factorial(n – 1)是不同的实体。

再来看一个示例。假设你要计算幂，就像内置函数pow和运算符**所做的那样。要定义一个数字的整数次幂，有多种方式，但先来看一个简单的定义：power(x, n)（x的n次幂）是将数字x自乘n - 1次的结果，即将n个x相乘的结果。换而言之，power(2, 3)是2自乘两次的结果，即2 × 2 × 2 = 8。

这实现起来很容易。

def power(x, n):

result = 1

for i in range(n):

result *= x

return result

这是一个非常简单的小型函数，但也可将定义修改成递归式的。

 对于任何数字x， power(x, 0)都为1。

 n>0时， power(x, n)为power(x, n-1)与x的乘积。

如你所见，这种定义提供的结果与更简单的迭代定义完全相同。理解定义是最难的，而实现起来很容易。

def power(x, n):

if n == 0:

return 1

else:

return x * power(x, n - 1)

我再次将定义从较为正规的文字描述转换成了编程语言（Python）。

提示 如果函数或算法复杂难懂，在实现前用自己的话进行明确的定义将大有裨益。以这种“准编程语言”编写的程序通常称为伪代码。

那么使用递归有何意义呢？难道不能转而使用循环吗？答案是肯定的，而且在大多数情况下，使用循环的效率可能更高。然而，在很多情况下，使用递归的可读性更高，且有时要高得多，在你理解了函数的递归式定义时尤其如此。另外，虽然你完全能够避免编写递归函数，但作为程

序员，你必须能够读懂其他人编写的递归算法和函数。