問題：一只青蛙一次可以跳上一級臺階远剩，也可以跳上兩級臺階扣溺。求該青蛙跳上n級臺階總共有多少種跳法？
思路：要跳上 第n級 臺階瓜晤，要么從第 n-1 級臺階跳上锥余，要么從第 n-2 級臺階跳上，只有這兩種方法痢掠。因此驱犹，跳上 第n級 臺階的跳法等于跳上 第n-1級 的跳法 加上 跳上第n-2級的跳法。采用遞歸算法實現(xiàn)雄驹。
基線條件：if n == 0 or n == 1 or n == 2: return n
遞歸公式：f(n) = f(n-1) + f(n-2)
代碼：
def stairs(n):
# 基線條件 => 跳出遞歸調(diào)用
if n == 0 or n == 1 or n == 2:
return n
# 遞歸公式：實現(xiàn)遞歸調(diào)用
return stairs(n-1) + stairs(n - 2)
print(stairs(5))
>>>
8
2020年11月30日修改：
使用遞歸求解，當(dāng)臺階數(shù)n過大時(>50)锌云，就會比較耗時了吁脱；
因此需要更改方式桑涎，觀察規(guī)律可知：f(n) = f(n-1) + f(n-2)，屬于斐波那契數(shù)列攻冷。
故代碼如下：
def stairs(n):
n1 = 1 # 一級臺階跳法數(shù)
n2 = 2 # 二級臺階跳法數(shù)
# 一級、二級臺階直接返回遍希，三級臺階以上循環(huán)計算n級臺階前兩級跳法和
# 例如：n = 3，n3 = n1 + n2，由于只使用兩個位置存儲數(shù)值禁谦，則需要更新n1, n2
# n2 = n1 + n2, n1 = n2。以繼續(xù)計算n>3的情況州泊。（最后n2即為結(jié)果）
if n == 1:
return n1
elif n == 2:
return n2
else:
for i in range(3, n + 1):
n1, n2 = n2, n1 + n2
return n2
補(bǔ)充：
1）遞歸函數(shù)優(yōu)點(diǎn) => 定義簡單丧蘸，邏輯清晰遥皂；
缺點(diǎn)：使用遞歸函數(shù)需要注意防止棧溢出。
遞歸調(diào)用時使用棧來保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場演训，也很耗費(fèi)資源弟孟。
2）計算機(jī)中，函數(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)致棧溢出。(RuntimeError: maximum recursion depth exceeded in comparison = > 運(yùn)行錯誤：超出最大遞歸深度试伙。)
python默認(rèn)棧的層數(shù)為1000層
3）使用尾遞歸進(jìn)行優(yōu)化：在遞歸函數(shù)返回的遞歸公式中直接調(diào)用自身本身嘁信，而不是返回計算表達(dá)式。這樣疏叨，編譯器或者解釋器就可以把尾遞歸做優(yōu)化潘靖，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀蚤蔓，不會出現(xiàn)棧溢出的情況卦溢。
需要每次調(diào)用時都直接計算結(jié)果，并將每次調(diào)用的前結(jié)果暫存起來秀又。
4）遺憾的是单寂，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化吐辙，所以宣决，即使把遞歸函數(shù)改成尾遞歸方式，也會導(dǎo)致棧溢出昏苏。
尾遞歸：
# 尾遞歸計算num的階乘
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)用。
