一、递归特性:
1. 必须有一个明确的结束条件
2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
3. 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，
栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）
1 def num(n):
2 print(n)
3 if int(n / 2) == 0:
4 return n
5 return num(int(n / 2))
6 num(10)
7 输出：
8 10
9 5
10 2
11 1
二、递归问路
1 import time
2 person_list = ['s1','s2','s3','s4','s5']
3 def ask_way(person_list):
4 print('-' * 60)
5 if len(person_list) == 0:
6 return "非常抱歉，我也不知道这个地方在哪儿."
7 person = person_list.pop(0)
8 if person == 's4':
9 return "%s说：这个地方刚好在我家附近，我可以带你去."%person
10 print("hello 帅锅[%s]请问你知道这个地方吗？"%person)
11 print("%s说：非常抱歉，我也不知道这个地方在哪儿.不过看你长得那么好看，我帮你问问%s"%(person,person_list))
12 time.sleep(2)
13 res = ask_way(person_list)
14 # print('%s问的结果是: %res' % (person, res))
15 return res
16 res = ask_way(person_list)
17 print(res)
三、二分查找
1 data = [1, 3, 6, 7, 9, 12, 14, 16, 17, 18, 20, 21, 22, 23, 30, 32, 33, 35]
2
3 def binary_search(dataset, find_num):
4 print(dataset)
5
6 if len(dataset) > 1:
7 mid = int(len(dataset) / 2)
8 if dataset[mid] == find_num: # find it
9 print("找到数字", dataset[mid])
10 elif dataset[mid] > find_num: # 找的数在mid左面
11 print(" 33[31;1m找的数在mid[%s]左面 33[0m" % dataset[mid])
12 return binary_search(dataset[0:mid], find_num)
13 else: # 找的数在mid右面
14 print(" 33[32;1m找的数在mid[%s]右面 33[0m" % dataset[mid])
15 return binary_search(dataset[mid + 1:], find_num)
16 else:
17 if dataset[0] == find_num: # find it
18 print("找到数字啦", dataset[0])
19 else:
20 print("没的分了,要找的数字[%s]不在列表里" % find_num)
21 binary_search(data, 66)