python基础案例教程_Python基础教程 两个经典案例:阶乘和幂

2023-02-24 09:08:38

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)。

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

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

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

  • 作者:weixin_39634997
  • 原文链接:https://blog.csdn.net/weixin_39634997/article/details/110314300
    更新时间:2023-02-24 09:08:38