遞歸函數(shù)
閱讀目錄
楔子
在講今天的內(nèi)容之前梨睁，我們先來(lái)講一個(gè)故事娜饵，講的什么呢？從前有座山拴念，山里有座廟，廟里有個(gè)老和尚講故事政鼠，講的什么呢公般？從前有座山，山里有座廟官帘，廟里有個(gè)老和尚講故事刽虹，講的什么呢？從前有座山涌哲，山里有座廟阀圾，廟里有個(gè)老和尚講故事，講的什么呢涡真？從前有座山肾筐，山里有座廟，廟里有個(gè)老和尚講故事剧劝，講的什么呢......這個(gè)故事你們不喊停我能講一天抓歼！我們說(shuō)拢锹，生活中的例子也能被寫(xiě)成程序，剛剛這個(gè)故事蹋半，讓你們寫(xiě)充坑，你們?cè)趺磳?xiě)呀染突？
while True:
? ? story = "? ? 從前有個(gè)山辈灼，山里有座廟巡莹，廟里老和尚講故事，
? ? 講的什么呢骂远？?
? ? "? ? print(story)
你肯定是要這么寫(xiě)的腰根，但是，現(xiàn)在我們已經(jīng)學(xué)了函數(shù)了贸营，什么東西都要放到函數(shù)里去調(diào)用岩睁、執(zhí)行。于是你肯定會(huì)說(shuō)冰啃，我就這么寫(xiě)：
def story():
? ? s = """
? ? 從前有個(gè)山刘莹，山里有座廟，廟里老和尚講故事扇调，
? ? 講的什么呢抢肛？
? ? """? ? print(s)
? ? while True:
? ? story()
但是大家來(lái)看看，我是怎么寫(xiě)的熬芜！
def story():
? ? s = """
? ? 從前有個(gè)山福稳，山里有座廟，廟里老和尚講故事鼓拧，
? ? 講的什么呢季俩？
? ? """? ? print(s)
? ? story()
story()
先不管函數(shù)最后的報(bào)錯(cuò)，除了報(bào)錯(cuò)之外藐鹤，我們能看的出來(lái)赂韵，這一段代碼和上面的代碼執(zhí)行效果是一樣的。
初識(shí)遞歸
遞歸的定義——在一個(gè)函數(shù)里再調(diào)用這個(gè)函數(shù)本身
現(xiàn)在我們已經(jīng)大概知道剛剛講的story函數(shù)做了什么肄满，就是在一個(gè)函數(shù)里再調(diào)用這個(gè)函數(shù)本身质涛，這種魔性的使用函數(shù)的方式就叫做遞歸。
剛剛我們就已經(jīng)寫(xiě)了一個(gè)最簡(jiǎn)單的遞歸函數(shù)怒炸。
遞歸的最大深度——997
正如你們剛剛看到的阅羹，遞歸函數(shù)如果不受到外力的阻止會(huì)一直執(zhí)行下去教寂。但是我們之前已經(jīng)說(shuō)過(guò)關(guān)于函數(shù)調(diào)用的問(wèn)題，每一次函數(shù)調(diào)用都會(huì)產(chǎn)生一個(gè)屬于它自己的名稱(chēng)空間导梆，如果一直調(diào)用下去迂烁，就會(huì)造成名稱(chēng)空間占用太多內(nèi)存的問(wèn)題，于是python為了杜絕此類(lèi)現(xiàn)象狡忙，強(qiáng)制的將遞歸層數(shù)控制在了997(只要997址芯！你買(mǎi)不了吃虧谷炸，買(mǎi)不了上當(dāng)...).
拿什么來(lái)證明這個(gè)“997理論”呢？這里我們可以做一個(gè)實(shí)驗(yàn)：
def foo(n):
? ? print(n)
? ? n += 1
? ? foo(n)
foo(1)
由此我們可以看出拓颓，未報(bào)錯(cuò)之前能看到的最大數(shù)字就是997.當(dāng)然了描孟，997是python為了我們程序的內(nèi)存優(yōu)化所設(shè)定的一個(gè)默認(rèn)值，我們當(dāng)然還可以通過(guò)一些手段去修改它：
import sysprint(sys.setrecursionlimit(100000))
我們可以通過(guò)這種方式來(lái)修改遞歸的最大深度场航，剛剛我們將python允許的遞歸深度設(shè)置為了10w廉羔，至于實(shí)際可以達(dá)到的深度就取決于計(jì)算機(jī)的性能了憋他。不過(guò)我們還是不推薦修改這個(gè)默認(rèn)的遞歸深度，因?yàn)槿绻?97層遞歸都沒(méi)有解決的問(wèn)題要么是不適合使用遞歸來(lái)解決要么是你代碼寫(xiě)的太爛了～～～
看到這里镀娶，你可能會(huì)覺(jué)得遞歸也并不是多么好的東西揪罕，不如while True好用呢！然而忍些，江湖上流傳這這樣一句話(huà)叫做：人理解循環(huán)坎怪，神理解遞歸搅窿。所以你可別小看了遞歸函數(shù)，很多人被攔在大神的門(mén)檻外這么多年男应，就是因?yàn)闆](méi)能領(lǐng)悟遞歸的真諦。而且之后我們學(xué)習(xí)的很多算法都會(huì)和遞歸有關(guān)系沐飘。來(lái)吧游桩，只有學(xué)會(huì)了才有資本嫌棄牲迫！
再談遞歸
這里我們又要舉個(gè)例子來(lái)說(shuō)明遞歸能做的事情。
例一：
現(xiàn)在你們問(wèn)我借卧，alex老師多大了盹憎？我說(shuō)我不告訴你，但alex比 egon 大兩歲铐刘。
你想知道alex多大陪每，你是不是還得去問(wèn)egon？egon說(shuō)镰吵，我也不告訴你檩禾，但我比武sir大兩歲疤祭。
你又問(wèn)武sir盼产，武sir也不告訴你，他說(shuō)他比金鑫大兩歲画株。
那你問(wèn)金鑫辆飘，金鑫告訴你，他40了谓传。蜈项。。
這個(gè)時(shí)候你是不是就知道了续挟？alex多大紧卒？
1金鑫 40
2武sir 42
3egon 44
4alex 46
你為什么能知道的？
首先诗祸，你是不是問(wèn)alex的年齡跑芳，結(jié)果又找到egon、武sir直颅、金鑫博个，你挨個(gè)兒?jiǎn)栠^(guò)去，一直到拿到一個(gè)確切的答案功偿，然后順著這條線(xiàn)再找回來(lái)盆佣，才得到最終alex的年齡。這個(gè)過(guò)程已經(jīng)非常接近遞歸的思想械荷。我們就來(lái)具體的我分析一下共耍，這幾個(gè)人之間的規(guī)律。
age(4) = age(3) + 2
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 40
那這樣的情況下吨瞎，我們的函數(shù)應(yīng)該怎么寫(xiě)呢痹兜？
def age(n):
? ? if n == 1:
? ? ? ? return 40
? ? else:
? ? ? ? return age(n-1)+2print(age(4))
遞歸函數(shù)與三級(jí)菜單
menu = {
? ? '北京': {
? ? ? ? '海淀': {
? ? ? ? ? ? '五道口': {
? ? ? ? ? ? ? ? 'soho': {},
? ? ? ? ? ? ? ? '網(wǎng)易': {},
? ? ? ? ? ? ? ? 'google': {}
? ? ? ? ? ? },
? ? ? ? ? ? '中關(guān)村': {
? ? ? ? ? ? ? ? '愛(ài)奇藝': {},
? ? ? ? ? ? ? ? '汽車(chē)之家': {},
? ? ? ? ? ? ? ? 'youku': {},
? ? ? ? ? ? },
? ? ? ? ? ? '上地': {
? ? ? ? ? ? ? ? '百度': {},
? ? ? ? ? ? },
? ? ? ? },
? ? ? ? '昌平': {
? ? ? ? ? ? '沙河': {
? ? ? ? ? ? ? ? '老男孩': {},
? ? ? ? ? ? ? ? '北航': {},
? ? ? ? ? ? },
? ? ? ? ? ? '天通苑': {},
? ? ? ? ? ? '回龍觀': {},
? ? ? ? },
? ? ? ? '朝陽(yáng)': {},
? ? ? ? '東城': {},
? ? },
? ? '上海': {
? ? ? ? '閔行': {
? ? ? ? ? ? "人民廣場(chǎng)": {
? ? ? ? ? ? ? ? '炸雞店': {}
? ? ? ? ? ? }
? ? ? ? },
? ? ? ? '閘北': {
? ? ? ? ? ? '火車(chē)戰(zhàn)': {
? ? ? ? ? ? ? ? '攜程': {}
? ? ? ? ? ? }
? ? ? ? },
? ? ? ? '浦東': {},
? ? },
? ? '山東': {},
}
1 def threeLM(dic): 2? ? while True: 3? ? ? ? for k in dic:print(k) 4? ? ? ? key = input('input>>').strip() 5? ? ? ? if key == 'b' or key == 'q':return key 6? ? ? ? elif key in dic.keys() and dic[key]: 7? ? ? ? ? ? ret = threeLM(dic[key]) 8? ? ? ? ? ? if ret == 'q': return 'q'9 10 threeLM(menu)
還記得之前寫(xiě)過(guò)的三級(jí)菜單作業(yè)么？現(xiàn)在咱們用遞歸來(lái)寫(xiě)一下～
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
