阶乘的求解
- 递归函数的定义
- 递归问题的拆解
- 递归的出口
递归函数的定义
递归算法的第一步，我们首先明确递归函数的定义，根据求解阶乘的需要我们首先定义myfactorial(n)函数，该函数的功能就是返回n!的值。
def myfactorial(n):#myfactorial函数功能：返回n!，参数为n
pass
递归的拆解
将求解的递归问题的规模拆解到能够十分容易被解决，在本例中我们很容易就可以想到，可以将求1*2*3……n的积，拆解成先求1~(n-1)的积再乘以n,即在数学上有myfactorial(n))=n*myfactorial(n-1)的等式成立，求1~n-1的积同样可以使用上述的方法进行拆解。程序表示如下：
def myfactorial(n):
s= n*myfactorial(n-1)*n#递归函数地拆解
return s
递归的出口
这里把递归函数的边界条件定义为n=0，也即是递归函数的出口。上述递归函数myfactorial(n)逐步拆解成myfactorial(0)时，返回值显然是1，可以将当n等于0，作为递归的出口(数学中0！=1,1！=1)
def myfactorial(n):
if n==0:
return 1 #递归的出口
s= n*myfactorial(n-1)#递归的拆解
return s
小结
根据阶乘递归算法，理解递归算法的三要素
掌握阶乘求解的递归算法
习题
- 画出myfactorial(5)递归调用执行过程图
- 尝试将递归函数myfactorial(n)的出口改为n=2，并验证