python学习笔记21——递归函数

如果一个函数在内部调用它本身，那么这个函数就是递归函数。

递归的条件：

①有调用函数自身的行为

②有一个正确的返回条件

例1：通过递归实现阶乘的运算（n！=1*2*3*...*(n-1)*n）

def fact(n):if n == 1:return 1else:return n * fact(n-1)

 n == 1时需要特殊处理。n == 5时，返回5*fact（4），fact(4)==4*fact(3)......以此类推，得到5的阶乘的结果。

2.斐波那契数列

F(n) = 1,当n=1时

F(n) = 1,当n=2时

F(n) = F(n-1)+F(n-2)，当n>2时

①使用迭代写出代码

def fab(n):n1 = 1n2 = 1n3 = 1if n < 1:print("输入有误！")return -1while (n-2) > 0:n3 = n2 + n1n1 = n2n2 = n3n -= 1return n3result = fab(20)
if result != -1:print("总共有%d对小兔诞生！"%result)

运行结果：

②使用递归写出代码

def fab(n):if n < 1:print("输入有误！")return -1if n == 1 or n == 2:return 1else:return fab(n-1) +fab(n-2)result = fab(20)
if result != -1:print("总共有%d对小兔诞生！"%result)

 运行结果：

 递归更契合分治思想。

迭代的效率更高，递归比较慢。