一、递归

  • 定义：在函数里面再调用这个函数本身
  • 递归的最大深度：理论值1000，具体看个人
  1. #查看自己电脑的递归最大深度的函数
  2. def foo(n):
  3.     print(n)
  4.     n += 1
  5.     foo(n)
  6. foo(1)

eg1：年龄问题
假设ABCDEF五个人，A问B你多大了 ，B说我比C大2岁，C说我比D大2岁，D说我比E大两岁，最后E说我20
求任意一人的年龄 

  1. def age(n):
  2.     if n == 1:
  3.         return 20
  4.     else:
  5.         return age(n-1)+2
  6. print(age(3))

eg2：递归实现三级菜单

  1. menu = {
  2.     '山东': {
  3.         '青岛': ['四方', '黄岛', '崂山', '李沧', '城阳'],
  4.         '济南': ['历城', '槐荫', '高新', '长青', '章丘'],
  5.         '烟台': ['龙口', '莱山', '牟平', '蓬莱', '招远']
  6.     },
  7.     '江苏': {
  8.         '苏州': ['沧浪', '相城', '平江', '吴中', '昆山'],
  9.         '南京': ['白下', '秦淮', '浦口', '栖霞', '江宁'],
  10.         '无锡': ['崇安', '南长', '北塘', '锡山', '江阴']
  11.     },
  12.     '浙江': {
  13.         '杭州': ['西湖', '江干', '下城', '上城', '滨江'],
  14.         '宁波': ['海曙', '江东', '江北', '镇海', '余姚'],
  15.         '温州': ['鹿城', '龙湾', '乐清', '瑞安', '永嘉']
  16.     },
  17.     '安徽': {
  18.         '合肥': ['蜀山', '庐阳', '包河', '经开', '新站'],
  19.         '芜湖': ['镜湖', '鸠江', '无为', '三山', '南陵'],
  20.         '蚌埠': ['蚌山', '龙子湖', '淮上', '怀远', '固镇']
  21.     },
  22.     '广东': {
  23.         '深圳': ['罗湖', '福田', '南山', '宝安', '布吉'],
  24.         '广州': ['天河', '珠海', '越秀', '白云', '黄埔'],
  25.         '东莞': ['莞城', '长安', '虎门', '万江', '大朗']
  26.     },
  27.     '山西': {}
  28. }
  29. import  time
  30. def threeLM(dic):
  31.     while True:
  32.         for k in dic:print(k)
  33.         key = input('input>>').strip()
  34.         if key == 'b' or key == 'q':return key
  35.         elif key in dic.keys() and dic[key]:
  36.             if isinstance(dic[key],list):
  37.                 for i in dic[key]:
  38.                     print(i)
  39.                 print('所有数据已经查询完毕即将返回上级菜单','==================================',sep='\n')
  40.                 time.sleep(3)
  41.                 continue
  43.             else:
  44.                 ret = threeLM(dic[key])
  45.                 if ret == 'q': return 'q'
  46.         else:
  47.             print('信息暂未录入请重新输入','=====================',sep='\n')
  48.             time.sleep(2)
  49.         continue
  51. threeLM(menu)

二、二分查找算法

必须是按序排好的

  1. 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]
  2. # def func(l,aim):
  3. #     mid = (len(l)-1)//2
  4. #     if l:
  5. #         if aim > l[mid]:
  6. #             func(l[mid+1:],aim)
  7. #         elif aim < l[mid]:
  8. #             func(l[:mid],aim)
  9. #         elif aim == l[mid]:
  10. #             print("找到了",mid)
  11. #     else:
  12. #         print('找不到')
  13. # func(l,66)
  14. # func(l,6)
  16. def search(num,l,start=None,end=None):
  17.     start = start if start else 0
  18.     end = len(l)-1 if end is None else end
  19.     mid = (end - start)//2 + start
  20.     if start > end:
  21.         return None
  22.     elif l[mid] > num :
  23.         return search(num,l,start,mid-1)
  24.     elif l[mid] < num:
  25.         return search(num,l,mid+1,end)
  26.     elif l[mid] == num:
  27.         return mid
  29. ret = search(18,l)
  30. print(ret)