上QQ阅读APP看书，第一时间看更新
3.2.4 实践演练——解决“阶乘”问题
为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解使用递归算法思想解决阶乘问题的方法。
1．问题描述
阶乘（factorial）是基斯顿·卡曼（Christian Kramp）于1808年发明的一种运算符号。自然数1～n连乘叫作n的阶乘，记作n!。
例如要求4的阶乘，则阶乘式是1×2×3×4，得到的积是24，即24就是4的阶乘。
例如要求6的阶乘，则阶乘式是1×2×3×…×6，得到的积是720，即720就是6的阶乘。
例如要求n的阶乘，则阶乘式是1×2×3×…×n，假设得到的积是x，x就是n的阶乘。
下面列出了0～10的阶乘。
0!=1
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
2．算法分析
假如计算6的阶乘，则计算过程如图3-2所示。
图3-2 计算6的阶乘的过程
3．具体实现
根据上述算法分析，下面的实例文件gui.py演示了使用递归算法计算并显示10之内的阶乘的过程。
源码路径：daima\第3章\gui.py
def fact(n):
print("factorial has been called with n = " + str(n))
if n == 1:
return 1
else:
res = n * fact(n - 1)
print("intermediate result for ", n, " * fact(", n - 1, "): ", res)
return res
print(fact(10))
执行后会输出：
factorial has been called with n = 10 factorial has been called with n = 9 factorial has been called with n = 8 factorial has been called with n = 7 factorial has been called with n = 6 factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * fact( 1 ): 2 intermediate result for 3 * fact( 2 ): 6 intermediate result for 4 * fact( 3 ): 24 intermediate result for 5 * fact( 4 ): 120 intermediate result for 6 * fact( 5 ): 720 intermediate result for 7 * fact( 6 ): 5040 intermediate result for 8 * fact( 7 ): 40320 intermediate result for 9 * fact( 8 ): 362880 intermediate result for 10 * fact( 9 ): 3628800 3628800