2.5　递归

递归是一种强大的技术，可以为各种问题提供优雅的解决方案。下面将介绍几个广为人知的问题，并通过递归来计算它们。

2.5.1　计算阶乘值

一个正整数n的阶乘等于从1到n的所有整数的乘积。阶乘用感叹号（!）来表示，下面是几个数字的阶乘值：

阶乘公式的简洁定义如下所示：

清单2.17的Factorial.py说明了如何通过递归计算一个正整数的阶乘。

清单2.17　Factorial.py

清单2.17包含一个函数factorial，它实现用递归方式计算一个数字的阶乘值。清单2.17的输出如下所示：

除了递归方式之外，还可以用迭代的方式计算数字的阶乘值。清单2.18的Factorial2.py说明了如何使用range()函数来计算一个正整数的阶乘值。

清单2.18　Factorial2.py

清单2.18定义一个函数factorial2()，接受一个形参num，并初始化变量prod为1。factorial2()之后是一个循环变量为x，并且值为从1到num+1的for循环。循环中的每个迭代用x的值乘以prod，由此计算num的阶乘值。清单2.18的输出如下所示：

2.5.2　计算斐波那契数

斐波那契数代表了自然界中一些有趣的模式（比如向日葵模式），它的递归定义如下：

清单2.19的fib.py说明了如何计算斐波那契数。

清单2.19　fib.py

清单2.19的代码定义一个函数fib()，接受一个形参num。当num为0或1的时候，fib()返回num；否则，fib()返回fib(num-1)和fib(num-2)之和。清单2.19的输出如下所示：

2.5.3　计算两个数的最大公约数

两个正整数的最大公约数（GCD）是指可以整除两个数的最大整数。比如：

清单2.20通过递归和欧几里得算法来查找两个数的最大公约数。

清单2.20　gcd.py

清单2.20定义一个函数gcd()，接受两个形参num1和num2。如果num1可以被num2整除就返回num2。如果num1小于num2，则调换num1和num2两个形参的位置调用gcd()；否则，就用num1-num2和num2作为形参调用gcd()。清单2.20的输出如下所示：

2.5.4　计算两个数的最小公倍数

两个正整数的最小公倍数（LCM）是两个数的倍数的最小整数。比如：

通常，两个正整数x和y，你可以按如下所示计算它们的最小公倍数：

清单2.21的代码使用前面定义的gcd()函数来计算两个正整数的最小公倍数。

清单2.21　lcm.py

清单2.21先定义一个前面讨论过的gcd()函数，之后定义一个lcm()函数接受两个形参num1和num2。lcm()的第一行使用gcd()计算num1和num2的最大公约数gcd1，第二行计算最小公倍数。最后输出lcm1的值。清单2.21的输出如下所示：