一兴垦、遞歸的定義
1.什么是遞歸：在一個(gè)函數(shù)里在調(diào)用這個(gè)函數(shù)本身
2.最大遞歸層數(shù)做了一個(gè)限制：997，但是也可以自己限制
def foo(n):
print(n)
n+=1
foo(n)
foo(1)
3.最大層數(shù)限制是python默認(rèn)的字柠，可以做修改探越，但是不建議你修改。（因?yàn)槿绻?97層遞歸都沒(méi)有解決的問(wèn)題要么是不適合使用遞歸來(lái)解決問(wèn)題窑业，要么就是你的代碼太爛了）
import sys
sys.setrecursionlimit(10000000)#修改遞歸層數(shù)
n=0
def f():
global n
n+=1
print(n)
f()
f()
我們可以通過(guò)以上代碼钦幔，導(dǎo)入sys模塊的方式來(lái)修改遞歸的最大深度。
sys模塊：所有和python相關(guān)的設(shè)置和方法
4.結(jié)束遞歸的標(biāo)志：return
5.遞歸解決的問(wèn)題就是通過(guò)參數(shù)常柄，來(lái)控制每一次調(diào)用縮小計(jì)算的規(guī)模
6.使用場(chǎng)景：數(shù)據(jù)的規(guī)模在減少鲤氢，但是解決問(wèn)題的思路沒(méi)有改變
7.很多排序算法會(huì)用到遞歸
二、遞歸小應(yīng)用
1.下面我們來(lái)猜一下小明的年齡
小明是新來(lái)的同學(xué)西潘，麗麗問(wèn)他多少歲了卷玉。
他說(shuō)：我不告訴你，但是我比滔滔大兩歲喷市。
滔滔說(shuō)：我也不告訴你揍庄，我比曉曉大兩歲
曉曉說(shuō)：我也不告訴你，我比小星大兩歲
小星也沒(méi)有告訴他說(shuō)：我比小華大兩歲
最后小華說(shuō)东抹，我告訴你蚂子，我今年18歲了
這個(gè)怎么辦呢？當(dāng)然缭黔，有人會(huì)說(shuō)食茎，這個(gè)很簡(jiǎn)單啊，知道小華的馏谨，就會(huì)知道小星的别渔，知道小星的就會(huì)知道曉曉的，以此類推惧互，就會(huì)知道小明的年齡啦哎媚。這個(gè)過(guò)程已經(jīng)非常接近遞歸的思想了。
| 姓名 | 年齡 |
|---|---|
| 小華 | 18+2 |
| 小星 | 20+2 |
| 曉曉 | 22+2 |
| 滔滔 | 24+2 |
| 小明 | 26+2 |
上面的圖我們可以用個(gè)序號(hào)來(lái)表示吧
age(5) = age(4)+2
age(4) = age(3) + 2
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 18
那么代碼該怎么寫呢喊儡？
def age(n):
if n == 1:
return 18
else:
return age(n - 1) + 2
ret=age(6)
print(ret)
2.一個(gè)數(shù)拨与，除2直到不能整除2
def cal(num):
if num % 2 == 0: ## 先判斷能不能整除
num = num // 2
return cal(num)
else:
return num
print(cal(8))
3.如果一個(gè)數(shù)可以整除2，就整除艾猜，不能整除就3+1*
def func(num):
print(num)
if num==1:
return
if num%2==0:
num=num//2
else:
num=num*3+1
func(num)
func(5)
三买喧、三級(jí)菜單
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'網(wǎng)易': {},
'google': {}
},
'中關(guān)村': {
'愛(ài)奇藝': {},
'汽車之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龍觀': {},
},
'朝陽(yáng)': {},
'東城': {},
},
'上海': {
'閔行': {
"人民廣場(chǎng)": {
'炸雞店': {}
}
},
'閘北': {
'火車戰(zhàn)': {
'攜程': {}
}
},
'浦東': {},
},
'山東': {},
}
==代碼實(shí)現(xiàn):==
def threeLM(menu):
while True:
for key in menu:#循環(huán)字典的key捻悯，打印出北京，上海淤毛，山東
print(key)
name=input('>>>:').strip()
if name=='back' or name=='quit':#如果輸入back今缚，就返回上一層。如果輸入quit就退出
return name #返回的name的給了ret
if name in menu:
ret=threeLM(menu[name])
if ret=='quit':return 'quit'#如果返回的是quit低淡，就直接return quit 了姓言，就退出了
threeLM()
## print(threeLM(menu))#print打印了就返回出quit了，threeLM()沒(méi)有打印就直接退出了
四蔗蹋、二分查找算法
從這個(gè)列表中找到55的位置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】
這就是二分查找事期，從上面的列表中可以觀察到，這個(gè)列表是從小到大依次遞增的有序列表纸颜。
按照上面的圖就可以實(shí)現(xiàn)查找了。
==簡(jiǎn)單的二分法==
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]
def find(l,aim):
mid=len(l)//2#取中間值绎橘，//長(zhǎng)度取整（取出來(lái)的是索引）
if l[mid]>aim:#判斷中間值和要找的那個(gè)值的大小關(guān)系
new_l=l[:mid]#顧頭不顧尾
return find(new_l,aim)#遞歸算法中在每次函數(shù)調(diào)用的時(shí)候在前面加return
elif l[mid]<aim:
new_l=l[mid+1:]
return find(new_l,aim)
else:
return l[mid]
print(find(l,66))
==升級(jí)版二分法==
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]
def func(l, aim,start = 0,end = len(l)-1):
mid = (start+end)//2#求中間的數(shù)
if not l[start:end+1]:#如果你要找的數(shù)不在里面胁孙，就return'你查找的數(shù)字不在這個(gè)列表里面'
return '你查找的數(shù)字不在這個(gè)列表里面'
elif aim > l[mid]:
return func(l,aim,mid+1,end)
elif aim < l[mid]:
return func(l,aim,start,mid-1)
elif aim == l[mid]:
print("bingo")
return mid
index = func(l,55)
print(index)
## print(func(l,41))
