問題：一只青蛙一次可以跳上一級臺階，也可以跳上兩級臺階。求該青蛙跳上n級臺階總共有多少種跳法？

思路：要跳上 第n級 臺階，要么從第 n-1 級臺階跳上，要么從第 n-2 級臺階跳上，只有這兩種方法。因此，跳上 第n級 臺階的跳法等于跳上 第n-1級 的跳法 加上 跳上第n-2級的跳法。采用遞歸算法實現。

基線條件：if n == 0 or n == 1 or n == 2: return n

遞歸公式：f(n) = f(n-1) + f(n-2)

代碼：

def stairs(n):

    # 基線條件 => 跳出遞歸調用
    if n == 0 or n == 1 or n == 2:
        return n
    
    # 遞歸公式：實現遞歸調用
    return stairs(n-1) + stairs(n - 2)


print(stairs(5))

>>>
8

2020年11月30日修改：
使用遞歸求解，當臺階數n過大時(>50)，就會比較耗時了；
因此需要更改方式，觀察規(guī)律可知：f(n) = f(n-1) + f(n-2)，屬于斐波那契數列。
故代碼如下：

def stairs(n):
    n1 = 1  # 一級臺階跳法數
    n2 = 2  # 二級臺階跳法數
    
    # 一級、二級臺階直接返回，三級臺階以上循環(huán)計算n級臺階前兩級跳法和
    # 例如：n = 3，n3 = n1 + n2，由于只使用兩個位置存儲數值，則需要更新n1, n2
    # n2 = n1 + n2, n1 = n2。以繼續(xù)計算n>3的情況。（最后n2即為結果）
    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

補充：

1）遞歸函數優(yōu)點 => 定義簡單，邏輯清晰；

缺點：使用遞歸函數需要注意防止棧溢出。

遞歸調用時使用棧來保護現場和恢復現場，也很耗費資源。

2）計算機中，函數調用是通過棧（stack）這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以，遞歸調用的次數過多，會導致棧溢出。(RuntimeError: maximum recursion depth exceeded in comparison = > 運行錯誤：超出最大遞歸深度。)

python默認棧的層數為1000層

3）使用尾遞歸進行優(yōu)化：在遞歸函數返回的遞歸公式中直接調用自身本身，而不是返回計算表達式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調用多少次，都只占用一個棧幀，不會出現棧溢出的情況。

需要每次調用時都直接計算結果，并將每次調用的前結果暫存起來。

4）遺憾的是，大多數編程語言沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化，所以，即使把遞歸函數改成尾遞歸方式，也會導致棧溢出。

尾遞歸：

# 尾遞歸計算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)僅返回遞歸函數本身，num - 1和num * product在函數調用前就會被計算，不影響函數調用。