在函數(shù)內部乏盐，可以調用其他函數(shù)烂斋，如果調用了函數(shù)本身，這個函數(shù)就是遞歸函數(shù)茬祷。
計算階乘
fact(n) = n! = 1 x 2 x 3 x ... x n = fact(n-1) x n
def fact(n):
if n == 1:
return 1
return n * fact(n-1)
使用遞歸函數(shù)需要防止棧溢出姑尺。在計算機中竟终，函數(shù)的調用是通過棧(stack)這種數(shù)據結構實現(xiàn)的，每當進入一個函數(shù)切蟋，棧就會加一層棧幀统捶，每當函數(shù)返回，就會減一層棧幀。由于棧的大小是有限的喘鸟，因此匆绣，遞歸調用次數(shù)過多會導致棧溢出。解決棧溢出的方法是尾遞歸優(yōu)化什黑。實際上崎淳，尾遞歸和循環(huán)的效果是一樣的。尾遞歸是指函數(shù)在返回的時候愕把，調用自身本身拣凹，且return語句不能包含表達式。這樣礼华，編譯器或解釋器可以把尾遞歸做優(yōu)化咐鹤，使得遞歸不論調用多少次，都只是用一個棧幀圣絮，不會出現(xiàn)棧溢出的情況祈惶。上面的函數(shù)中使用了return n * fact(n-1)，引用了乘法表達式扮匠，故不是尾遞歸捧请，應改為：
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)
遺憾的是，大多是編程語言設計都沒有針對尾遞歸做優(yōu)化棒搜，Python解釋器也沒有疹蛉，因此即使這樣改了也會出現(xiàn)棧溢出的問題。
漢諾塔問題
漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具力麸。大梵天創(chuàng)造世界的時候做了三根金剛石柱子可款，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上克蚂。并且規(guī)定闺鲸，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤埃叭。
<img src="https://ws1.sinaimg.cn/large/006tNc79gy1foonyqnegtj30go0gojsb.jpg"
style="zoom:50%" />
編寫函數(shù)move(n, x, y, z)摸恍，接收參數(shù)n，n表示三個柱子A赤屋、B立镶、C中第一個柱子A的盤子數(shù)量，然后打印出盤子從A借助B移動到C的方法：
# ~/usr/python_test/hannuota.py
def move(n, x, y, z):
if n == 1:
print(x, '-->', z)
return
else:
move(n-1, x, z, y)
move(1, x, y, z)
move(n-1, y, x, z)
return
move(4, 'A', 'B', 'C')
lijing@lijingdeMacBook-Pro > python3 ~/python_test/hannuota.py
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C
