學(xué)習(xí)網(wǎng)址：遞歸函數(shù)
注意重點(diǎn)：
遞歸函數(shù)的優(yōu)點(diǎn)是定義簡(jiǎn)單爽锥，邏輯清晰皱埠。理論上阁簸，所有的遞歸函數(shù)都可以寫(xiě)成循環(huán)的方式爬早，但循環(huán)的邏輯不如遞歸清晰。
使用遞歸函數(shù)需要注意防止棧溢出启妹。在計(jì)算機(jī)中筛严，函數(shù)調(diào)用是通過(guò)棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用饶米，棧就會(huì)加一層棧幀桨啃，每當(dāng)函數(shù)返回，棧就會(huì)減一層棧幀檬输。由于棧的大小不是無(wú)限的照瘾，所以，遞歸調(diào)用的次數(shù)過(guò)多丧慈，會(huì)導(dǎo)致棧溢出析命。
解決遞歸調(diào)用棧溢出的方法是通過(guò)尾遞歸優(yōu)化，事實(shí)上尾遞歸和循環(huán)的效果是一樣的逃默，所以鹃愤，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。
尾遞歸是指笑旺，在函數(shù)返回的時(shí)候昼浦，調(diào)用自身本身，并且筒主，return語(yǔ)句不能包含表達(dá)式关噪。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化乌妙，使遞歸本身無(wú)論調(diào)用多少次使兔，都只占用一個(gè)棧幀，不會(huì)出現(xiàn)棧溢出的情況藤韵。
尾遞歸調(diào)用時(shí)虐沥，如果做了優(yōu)化，棧不會(huì)增長(zhǎng)泽艘，因此欲险，無(wú)論多少次調(diào)用也不會(huì)導(dǎo)致棧溢出。
遺憾的是匹涮，大多數(shù)編程語(yǔ)言沒(méi)有針對(duì)尾遞歸做優(yōu)化天试，Python解釋器也沒(méi)有做優(yōu)化。
練習(xí)
漢諾塔的移動(dòng)可以用遞歸函數(shù)非常簡(jiǎn)單地實(shí)現(xiàn)然低。
請(qǐng)編寫(xiě)move(n, a, b, c)函數(shù)喜每，它接收參數(shù)n，表示3個(gè)柱子A雳攘、B带兜、C中第1個(gè)柱子A的盤(pán)子數(shù)量，然后打印出把所有盤(pán)子從A借助B移動(dòng)到C的方法吨灭。
看完題目之后有點(diǎn)蒙圈刚照，我們可以從簡(jiǎn)單地開(kāi)始遞推，如果只有一個(gè)盤(pán)子喧兄，直接A移動(dòng)到C（1步）涩咖，如果有兩個(gè)則A移動(dòng)到B，然后A移動(dòng)到C繁莹，然后B移動(dòng)到C（3步）檩互。3次的話(huà)需要7步。即3=2*1+1咨演；7=2*3+1闸昨。 那么f(n)=f(n-1)*2+1。很顯然隨著盤(pán)子數(shù)目的增多薄风，移動(dòng)次數(shù)指數(shù)級(jí)增長(zhǎng)饵较。
那么移動(dòng)又具體怎么實(shí)現(xiàn)呢？這里放上作者的代碼遭赂，各自理解理解：
# 利用遞歸函數(shù)移動(dòng)漢諾塔:
def move(n, a, b, c):
if n == 1:
print('move', a, '-->', c)
else:
move(n-1, a, c, b)
move(1, a, b, c)
move(n-1, b, a, c)
測(cè)試：
>>> move(4,"A","B","C")
move A --> B
move A --> C
move B --> C
move A --> B
move C --> A
move C --> B
move A --> B
move A --> C
move B --> C
move B --> A
move C --> A
move B --> C
move A --> B
move A --> C
move B --> C
