Python 進階：遞歸演算法的關鍵點剖析（階乘，斐波那契數列案例）

• 2020 年 4 月 19 日
• AI
• Python, 演算法

Python 中，遞歸是一種很多人都頭暈的演算法。
那在使用這個演算法的時候，怎樣可以更好地捋清楚思路呢？

首先我們來看案例：

一、求階乘

傳統實現方式：

def fact_for (x):
    r = 1
    for i in range(1,x+1):
        r *= i
    return r

遞歸實現方式：

def fact (x):
    if x!=1:
        r = x*fact(x-1)
        return r
    else:
        return x

二、斐波那契數列

傳統實現方法：

def fibonacci_for (x):
    if x < 1:
        return 0
    elif x == 1:
        return 1
    elif x == 2:
        return 1
    else:
        a = 1
        b = 1
        for i in range(2,x):
            c = a+b
            a,b = b,c
        return c

遞歸實現方式：

def fibonacci (x):
    if x < 1:
        return 0
    elif x == 1:
        return 1
    elif x == 2:
        return 1
    else:
        return fibonacci (x-1)+fibonacci (x-2)

三、遞歸的要點分析

1. 遞歸需要函數自己調用自己

比如前面 r = x*fact(x-1) 語句，和 fibonacci (x-1)+fibonacci (x-2) 語句。

2. 遞歸需要有個停止條件（防止無限遞歸）

比如求階乘的時候，當計算到 1 的時候，就要結束了。

3. 遞歸需要關注通項式

比如斐波那契數列的核心，就是第 n 個元素的值，為 n-1 和 n-2 這兩個值的和。

4. 注意點

Python 中默認的遞歸最大層數應該是 100 層。
當我們需要超過這個層數的時候，可以用以下語句設置：

import sys
sys.setrecursionlimit(100)

後面找時間再多補充幾個案例，請期待。。。