一、特点

　　递归算法是一种直接或者间接地调用自身算法的过程，再计算机编写程序中，递归算法对解决一大类问题是十分有效的。

　　1、递归就是在过程或函数里调用自身。

　　2、在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

　　3、递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

　　4、在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

二、要求

　　1、每次调用在规模上都有所缩小（通常是减半）；

　　2、相邻两次重复直接有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）；

　　3、在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的，无条件的递归将造成死循环而不能正常结束。

三、实例

1 def calc(n):2     print(n)3     if n/2 >1:4         res = calc(n/2)5         print('res:',res)6     print("N:",n)7     return n8 calc(10)

10 5.0 2.5 1.25 N: 1.25 res: 1.25 N: 2.5 res: 2.5 N: 5.0 res: 5.0 N: 10 四、斐波拉契数列

1 def func(arg1,arg2,stop):2     if arg1 == 0:3         print(arg1,arg2)4     arg3 = arg1 + arg25     print(arg3)6     if arg3 < stop:7         func(arg2,arg3,stop)8 9 func(0,1,30)

 

0 1

1

2

3

5

8

13

21

34

五、算法基础之二分查找

1 def binary_search(data_source,find_n): 2     mid = int(len(data_source)/2) 3     if len(data_source) > 1: 4         if data_source[mid] > find_n: #data in left 5             #print(data_source[:mid]) 6             binary_search(data_source[:mid],find_n) 7         elif data_source[mid] < find_n: #data in right 8             print("data in right of [%s]"%data_source[mid]) 9             #print(data_source[mid:])10             binary_search(data_source[mid:],find_n)11         else:12             print("found find_s ",data_source[mid])13     elif len(data_source) == 1:14         if find_n in data_source:15             print("found find_s",data_source[0])16     else:17         print("cannot find ...")18 if __name__ == "__main__":19     data = [1,2,3]20     binary_search(data,1)