一、递归函数
1.1、定义
在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。
1.2、递归函数特性
- 必须有一个明确的结束条件；
- 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
- 相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
- 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）
2.1、递归的最大深度——997
递归函数如果不受到外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题，每一次函数调用都会产生一个属于它自己的名称空间，如果一直调用下去，就会造成名称空间占用太多内存的问题，于是python为了杜绝此类现象，强制的将递归层数控制在了997
示例如下：
1 # 997理论 2 def foo(n): 3 print(n) 4 n += 1 5 foo(n) 6 foo(1) 7 # 结果 8 ... 9 99510 99611 99712 报错信息：RecursionError: maximum recursion depth exceeded while calling a Python object
由此我们可以看出，未报错之前能看到的最大数字就是997.当然了，997是python为了我们程序的内存优化所设定的一个默认值，我们当然还可以通过一些手段去修改它：
import sysprint(sys.setrecursionlimit(100000))
我们可以通过这种方式来修改递归的最大深度，刚刚我们将python允许的递归深度设置为了10w，至于实际可以达到的深度就取决于计算机的性能了。不过我们还是不推荐修改这个默认的递归深度。
2.2、递归的应用示例
示例1：
已知alex比egon大两岁，egon比wusir大两岁，wusir比无alan大两岁，alan为40岁，求alex的年龄
| 1 | 金鑫 | 40 |
| 2 | 武sir | 42 |
| 3 | egon | 44 |
| 4 | alex | 46 |
根据几个人的关系，分析结果如下：
age(4) = age(3) + 2 #alex的年龄age(3) = age(2) + 2 #egonage(2) = age(1) + 2 #wusirage(1) = 40 #alan
因此，计算Alex年龄的递归函数如下：
def age(n): if n == 1: return 40 else: return age(n-1)+2 print(age(4)) #46
示例2：
递归函数与三级菜单
#三级菜单menu = { '北京': { '海淀': { '五道口': { 'soho': {}, '网易': {}, 'google': {} }, '中关村': { '爱奇艺': {}, '汽车之家': {}, 'youku': {}, }, '上地': { '百度': {}, }, }, '昌平': { '沙河': { '老男孩': {}, '北航': {}, }, '天通苑': {}, '回龙观': {}, }, '朝阳': {}, '东城': {}, }, '上海': { '闵行': { "人民广场": { '炸鸡店': {} } }, '闸北': { '火车战': { '携程': {} } }, '浦东': {}, }, '山东': {},} #递归函数实现三级菜单def threeLM(dic): while True: for k in dic:print(k) key = input('input>>').strip() #按b键返回上一级，按q键则退出函数 if key == 'b' or key == 'q':return key elif key in dic.keys() and dic[key]: ret = threeLM(dic[key]) if ret == 'q': return 'q'threeLM(menu)#结果如下北京上海山东input>>北京海淀昌平朝阳东城input>>海淀五道口中关村上地input>>五道口soho网易googleinput>>sohosoho网易googleinput>> #堆栈实现三级菜单def StackThreeLM(dic): l = [menu] while l: for key in l[-1]:print(key) k = input('input>>').strip() # 北京 if k in l[-1].keys() and l[-1][k]:l.append(l[-1][k]) elif k == 'b':l.pop() #返回上一级 elif k == 'q':break #退出操作StackThreeLM(menu)
二、二分查找算法
l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] 比如从这个有序列表中，要查找66的索引，二分查找66索引位置的实现过程如下：
二分查找算法代码如下：
#二分查找算法def find(l,aim,start=0,end=None): if end == None:end = len(l)-1 if start <= end: mid = (end - start) // 2 + start if l[mid] > aim: return find(l,aim,start=start,end=mid-1) elif l[mid] < aim: return find(l,aim,start=mid+1,end=end) elif l[mid] == aim: return mid else: return Nonel = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]print('ret :',find(l,66)) #ret : 17