一，什么叫递归
#递归
#在一个函数里调用自己
#python递归最大层数限制 997
#最大层数限制是python默认的，可以做修改
#但是我们不建议你修改
例子和尚讲故事
1 #!/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 4 #:基础版本 5 def story(): 6 print("从前有座山，山里有座庙，庙里有个老和尚讲故事，讲的什么呀?") 7 while True: 8 story() 9 10 #:递归版本 11 def story(): 12 #递归函数，在一个函数内调用自己 13 #最大递归层数做了一个限制：997 14 print("从前有座山，山里有座庙，庙里有个老和尚讲故事，讲的什么呀?") 15 story() 16 print('123') 17 story()
修改深度
1 #!/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 4 import sys #所有和python相关的设置和方法 5 sys.setrecursionlimit(10000000) 6 n = 0 7 def f(): 8 global n 9 n += 1 10 print(n) 11 f() 12 f()
二，递归实例
递归实现三级菜单
1 #!/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 4 #三级菜单，按B返回 5 menu = { 6 '北京': { 7 '海淀': { 8 '五道口': { 9 'soho': {}, 10 '网易': {}, 11 'google': {} 12 }, 13 '中关村': { 14 '爱奇艺': {}, 15 '汽车之家': {}, 16 'youku': {}, 17 }, 18 '上地': { 19 '百度': {}, 20 }, 21 }, 22 '昌平': { 23 '沙河': { 24 '老男孩': {}, 25 '北航': {}, 26 }, 27 '天通苑': {}, 28 '回龙观': {}, 29 }, 30 '朝阳': {}, 31 '东城': {}, 32 }, 33 '上海': { 34 '闵行': { 35 "人民广场": { 36 '炸鸡店': {} 37 } 38 }, 39 '闸北': { 40 '火车战': { 41 '携程': {} 42 } 43 }, 44 '浦东': {}, 45 }, 46 '山东': {}, 47 } 48 print('主菜单'.center(40,'=')) 49 # while True: 50 # for i in menu:print(i) 51 # user1 = input('no 1>>>:') 52 # if user1 == 'b':break 53 # if user1 == 'q':exit() 54 # if user1 not in menu:continue 55 # if user1 in menu: 56 # while True: 57 # for i1 in menu[user1]: print(i1) 58 # user2 = input('no 2>>>:') 59 # if user2 == 'b': break 60 # if user2 == 'q': exit() 61 # if user2 not in menu[user1]: continue 62 # if user2 in menu[user1]: 63 # while True: 64 # for i2 in menu[user1][user2]: print(i2) 65 # user3 = input('no 3>>>:') 66 # if user3 == 'b': break 67 # if user3 == 'q': exit() 68 # if user3 not in menu[user1][user2]: continue 69 # if user3 in menu[user1][user2]: 70 # while True: 71 # user4 = input('no 4>>>:') 72 # if user4 == 'b':break 73 # if user4 == 'q':exit() 74 75 def list(menu): #menu being 76 while True: 77 for i in menu: 78 print(i) 79 k = input('>>>').strip()##beijng 80 if k == 'b' or k =='q': #k 81 return k #diyi beijing 82 if k in menu: 83 ret = list(menu[k]) #menu shahe 84 if ret == 'q':return 'q' 85 index = list(menu) 86 print(index)
递归实现二分查找
1 #!/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 4 #二分查找算法 5 #算法：计算的方法 6 #有序的递增列表 7 #查找的是数字 8 l = [2,3,5,10,15,16,18,22,26] 9 def find(l,aim): #l:列表 aim：要找的 10 mid = len(l)//2 #计算中点 11 if l[mid] > aim: #判断中间位置的值和目标值的大小关系 12 new_l = l[:mid] #[16,18] = [16,18,22,26][:mid] 13 return find(new_l,aim) 14 elif l[mid] < aim:#判断中间位置的值和目标值的大小关系 15 new_l = l[mid+1:] 16 return find(new_l,aim) 17 else: 18 return l[mid] 19 print(find(l,16)) 20 21 #升级版二分法 22 #查找的是索引 23 l = [2,3,5,10,15,16,18,22,26] 24 def find2(l,aim,start,end):#[2,3,5,10,15,16,18,22,26] 0,8 25 mid = (end+start)//2 #4 #5+8/2=6 #start =5 end = 5 mid = 5 26 if start < end: 27 if l[mid] > aim: #15 17 #18 17 28 end = mid -1 #end =6-1 = 5 29 return find2(l,aim,start,end) 30 elif l[mid] < aim: #15 17 31 start = mid + 1 # start = 5 32 return find2(l, aim, start, end) 33 else: 34 return mid 35 else: 36 return "找不到" 37 print(find2(l,18,start=0,end = len(l)-1)) 38 39 #高级版二分法 40 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] 41 def func(l, aim,start = 0,end = len(l)-1 ): 42 mid = (start+end)//2 43 print(l[start:end+1]) 44 if not l[start:end+1]: #空就是False not 就是 true 45 return 46 elif aim > l[mid]: 47 return func(l,aim,mid+1,end) 48 elif aim < l[mid]: 49 return func(l,aim,start,mid-1) 50 elif aim == l[mid]: 51 print("bingo") 52 return mid 53 index = func(l,1)
三，总结
#递归解决的问题
#就是通过参数，来控制每一次调用缩小计算的规模
#适合的场景
#数据的规模在减小，但是解决问题的思路没有改变
#结束递归的标志：return