递归，二分法

1.递归

1.必须有一个明确的结束条件

2.每次进入更深一次的递归时，问题规模相比上次都应有所减少

3.递归效率不高，递归层次过多会导致栈溢出。

 1 import time
 2 def age(n):
 3     print('====>',n)
 4     time.sleep(1)
 5     if n == 1:
 6         return 10
 7     else:
 8         return age(n-1)+2
 9 print(age(5))
10 
11 #n=1,res=10
12 #n>1,res=age(n-1)+2
13 
14 
15 
16 
17 ====> 5
18 ====> 4
19 ====> 3
20 ====> 2
21 ====> 1
22 18

2.二分法

 1 data = [1, 3, 6, 7, 9, 12, 14, 16, 17, 18, 20, 21, 22, 23, 30, 32, 33, 35]
 2 
 3 def search(num,data):
 4     print(data)
 5     if len(data) > 1:   #二分
 6         mid_index=int(len(data)/2)
 7         mid_value=data[mid_index]
 8         if num > mid_value:
 9             #num在列表的右边
10             data=data[mid_index:]
11             search(num,data)
12         elif num < mid_value:
13             #num在列表的左边
14             data=data[:mid_index]
15             search(num,data)
16         else:
17             print('find it')
18             return
19     else:
20         if data[0] == num:
21             print('find it')
22         else:
23             print('not exists')
24 
25 search(17,data)
26 
27 
28 
29 
30 
31 [1, 3, 6, 7, 9, 12, 14, 16, 17, 18, 20, 21, 22, 23, 30, 32, 33, 35]
32 [1, 3, 6, 7, 9, 12, 14, 16, 17]
33 [9, 12, 14, 16, 17]
34 [14, 16, 17]
35 [16, 17]
36 find it