在函數(shù)內(nèi)部，可以調(diào)用其他函數(shù)寻歧。如果一個函數(shù)在內(nèi)部調(diào)用自身本身阁谆，這個函數(shù)就是遞歸函數(shù)煤搜。
在函數(shù)內(nèi)部酣溃，可以調(diào)用其他函數(shù)。如果一個函數(shù)在內(nèi)部調(diào)用自身本身烛愧，這個函數(shù)就是遞歸函數(shù)音念。
舉個例子氯哮，我們來計算階乘n! = 1 x 2 x 3 x ... x n际跪，用函數(shù)fact(n)表示，可以看出：
fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n
所以喉钢，fact(n)可以表示為n x fact(n-1)姆打，只有n=1時需要特殊處理。
于是出牧，fact(n)用遞歸的方式寫出來就是：
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
遞歸函數(shù)的優(yōu)點是定義簡單穴肘，邏輯清晰。理論上舔痕，所有的遞歸函數(shù)都可以寫成循環(huán)的方式，但循環(huán)的邏輯不如遞歸清晰豹缀。
使用遞歸函數(shù)需要注意防止棧溢出伯复。在計算機中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的邢笙，每當(dāng)進(jìn)入一個函數(shù)調(diào)用啸如，棧就會加一層棧幀，每當(dāng)函數(shù)返回氮惯，棧就會減一層棧幀叮雳。由于棧的大小不是無限的，所以妇汗，遞歸調(diào)用的次數(shù)過多帘不，會導(dǎo)致棧溢出⊙罴可以試試fact(1000)：
>>> fact(1000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 4, in fact
...
File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison
解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化寞焙，事實上尾遞歸和循環(huán)的效果是一樣的，所以互婿，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的捣郊。
尾遞歸是指，在函數(shù)返回的時候慈参，調(diào)用自身本身呛牲，并且，return語句不能包含表達(dá)式驮配。這樣娘扩，編譯器或者解釋器就可以把尾遞歸做優(yōu)化尊勿，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀畜侦，不會出現(xiàn)棧溢出的情況元扔。
果一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個遞歸函數(shù)是尾遞歸的旋膳。當(dāng)遞歸調(diào)用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分時澎语，這個遞歸調(diào)用就是尾遞歸。尾遞歸函數(shù)的特點是在回歸過程中不用做任何操作验懊，這個特性很重要擅羞，因為大多數(shù)現(xiàn)代的編譯器會利用這種特點自動生成優(yōu)化的代碼。
尾遞歸通過計數(shù)來控制步驟义图，在每個步驟傳達(dá)具體的數(shù)减俏，而不是計算式。從而降低對棧的占用碱工。
上面的fact(n)函數(shù)由于return n * fact(n - 1)引入了乘法表達(dá)式娃承，所以就不是尾遞歸了。要改成尾遞歸方式怕篷，需要多一點代碼历筝，主要是要把每一步的乘積傳入到遞歸函數(shù)中：
def fact(n):
return fact_iter(n, 1)
def fact_iter(num, product):
if num == 1:
return product
return fact_iter(num - 1, num * product)
可以看到，return fact_iter(num - 1, num * product)僅返回遞歸函數(shù)本身廊谓，num - 1和num * product在函數(shù)調(diào)用前就會被計算梳猪，不影響函數(shù)調(diào)用。
fact(5)對應(yīng)的fact_iter(5, 1)的調(diào)用如下：
===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120
尾遞歸調(diào)用時蒸痹，如果做了優(yōu)化春弥，棧不會增長，因此叠荠，無論多少次調(diào)用也不會導(dǎo)致棧溢出匿沛。
遺憾的是，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化蝙叛，Python解釋器也沒有做優(yōu)化俺祠，所以，即使把上面的fact(n)函數(shù)改成尾遞歸方式借帘，也會導(dǎo)致棧溢出蜘渣。
小結(jié)
使用遞歸函數(shù)的優(yōu)點是邏輯簡單清晰，缺點是過深的調(diào)用會導(dǎo)致棧溢出肺然。
針對尾遞歸優(yōu)化的語言可以通過尾遞歸防止棧溢出蔫缸。尾遞歸事實上和循環(huán)是等價的，沒有循環(huán)語句的編程語言只能通過尾遞歸實現(xiàn)循環(huán)际起。
Python標(biāo)準(zhǔn)的解釋器沒有針對尾遞歸做優(yōu)化拾碌，任何遞歸函數(shù)都存在棧溢出的問題吐葱。
練習(xí)
漢諾塔的移動可以用遞歸函數(shù)非常簡單地實現(xiàn)。
請編寫move(n, a, b, c)函數(shù)校翔，它接收參數(shù)n弟跑，表示3個柱子A、B防症、C中第1個柱子A的盤子數(shù)量孟辑，然后打印出把所有盤子從A借助B移動到C的方法。
漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具蔫敲。大梵天創(chuàng)造世界的時候做了三根金剛石柱子饲嗽，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上奈嘿。并且規(guī)定貌虾，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤裙犹。
解題：
1）把盤子在原始柱子上從上往下尽狠，從1開始整數(shù)編號，那么小序號的盤子一定要在大序號的盤子之上伯诬。
2）當(dāng)?shù)趎個盤子被從A柱移到C 柱時晚唇，它一定是A柱的最后一個盤子，移開之后A柱子空了盗似；它一定是C柱第一個盤子，移來之前C柱子是空的平项。
3）第n個盤子移到C柱子后赫舒，整個局面變成了（n-1)局面： B柱上是從1-（n-1）排列的盤子，A柱空闽瓢，我們的問題變成了將這（n-1）個盤子,從b柱上經(jīng)過a柱接癌，按照原來的規(guī)矩全部移動到C柱上去。
所以扣讼，這就是一個典型的遞歸問題缺猛。
def hanoi(n,a,b,c):
if n == 1:
print (a,' ==> ', c)
else:
hanoi(n-1,a,c,b) #將前n-1個盤子移動到b上
hanoi(1,a,b,c) #將最底下一個盤子從a移動到c上
hanoi(n-1,b,a,c) #開始下一個步驟，將b上的n-1個盤子移到 c上
hanoi(3,'A','B','C')
('A', ' ==> ', 'C')
('A', ' ==> ', 'B')
('C', ' ==> ', 'B')
('A', ' ==> ', 'C')
('B', ' ==> ', 'A')
('B', ' ==> ', 'C')
('A', ' ==> ', 'C')
[Finished in 0.0s]
