第022讲：函数：递归是神马

0.递归在编程上的形式是如何表现的呢？

答：在编程上，递归表现为函数调用本身这么一个行为。

举个例子（递归求阶乘）：

def factorial(n):

if n ==1:

return 1

else:

return n * factorial(n-1)

number = int(input('请输入一个整数：'))

result = factorial(number)

print("%d的阶乘是：%d" % (number,result))

1.递归必须满足哪两个基本条件？

答：

一、函数调用自身

二、设置了正确的返回条件

2.思考一下，按照递归的特性，在编程中有没有不得不使用递归的情况？

答：例如汉诺塔，目录索引（因为你永远不知道这个目录里面是否还有目录），快速排序（二十世纪十大算法之一），树结构的定义等如果使用递归，会事半功倍，否则会导致程序无法实现或相当难以理解。

3.用递归去计算阶乘问题或裴波那契数列是很糟糕的算法，你知道为什么吗？

4.请聊聊递归的优缺点

动动手：

0.使用递归编写一个power()函数模拟内建函数pow()，即power(x,y)为计算并返回x的y次幂的值。

def power(x,y):

if y:

return x * power(x,y-1)

else:

return 1

print(power(2,3))

1.使用递归编写一个函数，利用欧几里得算法求最大公约数，例如gcd(x,y)返回值为参数x和参数y的最大公约数。

def gcd(x,y):

if y:

return gcd(y,x%y)

else:

return x

print(gcd(4,6))