递归函数
1. 递归（recursion）一个函数在内部调用了自己，这种写法就叫做递归。
def func(): # 每次调用一个函数，就会开辟一块内存空间
print("djgdl")
func() # 在内部调用自己
print(123) # 这句话不会打印
func()
2. 关于递归函数
1. 递归函数必须有一个结束条件，递归并不是无限制的，在python中默认最大深度是997或998。
2. 分析的流程拿到返回值，到一个结束条件的时候叫做递，返回值计算的时候叫做归。一定有递推的过程，不一定有回归的过程。
3. 最大递归深度
import sys
sys.setrecursionlimit(100000000) # 修改递归最大深度，一般不要去修改
COUNT = 0
def func():
global COUNT
COUNT += 1
print(COUNT)
func()
func()
4. 二分查找（重点）
def search(num,l,start=None,end=None):
start = start if start else 0 # start是开始查找的位置
end = end if end else len(l)-1 # end是结束查找的位置
mid = (end - start) // 2 + start #//是取到整数
if start > end: # 这里是当要查找的值不存在的时候，就返回一个None
return None
elif l[mid] > num:
return search(num,l,start,mid-1)
elif l[mid] < num:
return search(num,l,mid+1,end)
elif l[mid] == num:
return mid,l[mid]
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]
print(search(66,l))
# 递推 ：这个程序只有递推的过程，没有回归返回值的过程
def search(66,l,start=None,end=None):
# 一开始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]
start = start if start else 0
end = end if end else 25-1
mid = (24 - 0) // 2 + 0 =12
elif 41 < 66:
return search(66,l,12+1,24)
def search(66,l,start=13,end=24): #search(66,l,12+1,24)
# 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]
start = start if start else 0
end = end if end else len(l)-1
mid = (24 - 13) // 2 + 13 =18
elif 67 > 66:
return search(66,l,13,17)
def search(66,l,start=13,end=17): #search(66,l,13,17)
# 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]
start = start if start else 0
end = end if end else len(l)-1
mid = (17 - 13) // 2 + 13 = 15
elif 55 < 66:
return search(66,l,17,17)
def search(66,l,start=16,end=17): #search(66,l,16,17)
# 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]
start = start if start else 0
end = end if end else len(l)-1
mid = (17 - 17) // 2 + 17
elif 66 == 66:
return 17,66
示例一： 1 的年龄问题 ，1 的年龄不知道，比 2 大2岁，2 比 3 大2岁，3 比 4 大2岁，4 的年龄是40
def age(n):
if n == 4:
return 40
return age(n+1)+2
ret = age(1)
print(ret)
# 递的过程：
def age(1):
return age(1+1)+2
def age(2):
return age(2+1)+2
def age(3):
return age(3+1)+2
def age(4):
if n == 4:
return 40
# 归的过程,从下往上返回值
age(1) = 46
def age(1):
return age(2)+2
age(2) = 44
def age(2):
return age(3)+2
age(3) = 42
def age(3):
return age(4)+2
age(4) = 40
def age(4):
if n == 4:
return 40
示例二： 求阶乘 7*6*5*4*3*2*1
def func(n):
if n == 1:
return n
return n*func(n-1)
ret = func(7)
print(ret)
# 递推
def func(7):
return 7*func(7-1)
def func(6):
return 6*func(6-1)
def func(5):
return 5*func(5-1)
def func(4):
return 4*func(4-1)
def func(3):
return 3*func(3-1)
def func(2):
return 2*func(2-1)
def func(1):
if 1 == 1:
return 1
# 回归
func(7)=5040
def func(7):
return 7*func(7-1)
func(6)=720
def func(6):
return 6*func(6-1)
func(5)=120
def func(5):
return 5*func(5-1)
func(4)=24
def func(4):
return 4*func(4-1)
func(3)=6
def func(3):
return 3*func(3-1)
func(2)=2
def func(2):
return 2*func(1)
func(1)=1
def func(1):
if 1 == 1:
return 1
示例三：三级菜单
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
def three_menu(menu):
while True:
for k in menu:print(k)
key = input(">>>")
if key.lower() =="q":return "q" # return 一个q 就需要有变量去接收
elif key == "b":break # 当输入b的时候，就break，这里break是只能返回上一层，是因为有while，如果单独return和break的效果是一样的，所以下面才需要有个变量去接受
elif key in menu:
ret = three_menu(menu[key]) # 这里的ret就是去接收return回来的 q 的
if ret == "q":return "q" # 当ret=q的时候，就直接再return q 这样就保证了用户输入q，就会直接退出
three_menu(menu)