Python 递归

一、特点

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

　　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 n
8 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 + arg2
5     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)