はじめに

フィボナッチ数列とは、「最初の二項は 0, 1 であり、以後どの項もその直前の2つの項の和となっている数列」です。（ウィキベディアより）

フィボナッチ数列

0
1
1 （0 + 1）
2 （1 + 1）
3 （1 + 2）
5 （2 + 3）
8 （3 + 5）
13 （5 + 8）

この数列のn番目の項を求めるとき、そのまま実装するとこのようになります。

def fib(n):
    """
    ０始まりでn番目のフィボナッチ数を求める。
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

print(fib(7)) # -> 13

実際に実行してみると、とても遅いことがわかります。
例えば、n=100でも相当な時間がかかります。

その原因は、詳細は割愛しますが、同じ計算を何度も行なっている点にあります。
例えば、fib(8)は、fib(7)とfib(6)をそれぞれ求めた上で足し合わせて求められますが、fib(7)を求めるためにはfib(6)を新たに求める必要があります。

「同じ計算を二度しない」をキーワードに、高速化をしてみましょう。
メモ化と動的計画法の二つのアルゴリズムを紹介します。

メモ化

一度計算した結果を保存しておきます。
使える場合はそれを使い、そうでない場合は新たに計算し、その結果を次回以降のために保存しておきます。

MAX_N = 100
MEMO = [None] * (MAX_N + 1)  # 計算結果を保存する配列

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    # 計算済み？
    if MEMO[n]:
        return MEMO[n]

    r = fib(n-1) + fib(n-2)
    MEMO[n] = r  # 計算結果を保存
    return r

print(fib(100))

n=100の場合でもすぐに結果が帰ってきました。

動的計画法（DP）

再帰関数を使わなくても、nが小さい方から計算することで、フィボナッチ数を求めることができます。

MAX_N = 100
DP = [None] * (MAX_N + 1)  # 計算結果を保存する配列
DP[0] = 0  # 定義より
DP[1] = 1  # 定義より

def fib(n):
    # フィボナッチ数を2からnまで順に求めていく
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    return DP[n]

print(fib(100))

動的計画法については、参考資料を見てください。

参考資料

https://www.slideshare.net/iwiwi/ss-3578511