n番目のフィボナッチ数を求めるPythonプログラム【再帰・動的計画法】

本記事では、n番目のフィボナッチ数を計算するPythonプログラムについて解説します。

フィボナッチ数とは？

フィボナッチ数とは、次の漸化式で定義される数列のことです。

Fn = Fn-1 + Fn-2

ただし、初期値は F₀ = 0、F₁ = 1 とします。

フィボナッチ数列の最初のいくつかの値は以下の通りです。

0, 1, 1, 2, 3, 5, 8, 13, ..................

フィボナッチ数は、再帰と動的計画法（Dynamic Programming）という2つの代表的な手法で求めることができます。それでは、それぞれの実装方法をPythonスクリプトで見ていきましょう。

方法1：再帰を使うアプローチ

コード例

# 再帰によるアプローチ
def Fibonacci(n):
    if n<0:
        print("Fibonacci can't be computed")
    # 第1フィボナッチ数
    elif n==1:
        return 0
    # 第2フィボナッチ数
    elif n==2:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
# メイン処理
n=10
print(Fibonacci(n))

実行結果

34

宣言されたすべての変数のスコープは下図のように示されます。

この再帰的な実装では、各関数呼び出しがさらに2つの再帰呼び出しを生成するため、計算量は指数関数的な O(2ⁿ) になります。そのため、n が大きくなると処理が非常に遅くなる点に注意が必要です。

方法2：動的計画法を使うアプローチ

コード例

# 動的計画法によるアプローチ
Fib_Array = [0,1]
def fibonacci(n):
    if n<0:
        print("Fibonacci can't be computed")
    elif n<=len(Fib_Array):
        return Fib_Array[n-1]
    else:
        temp = fibonacci(n-1)+fibonacci(n-2)
        Fib_Array.append(temp)
        return temp
# ドライバープログラム
n=10
print(fibonacci(n))

実行結果

34

宣言されたすべての変数のスコープは下図のように示されます。

この実装では、一度計算した値をリストにキャッシュするメモ化の考え方を取り入れています。これにより、同じ値を何度も再計算する無駄がなくなり、計算量は O(n) まで大幅に改善されます。

まとめ

本記事では、再帰と動的計画法という2つのアプローチを用いて、n番目のフィボナッチ数を計算するPythonプログラムを紹介しました。小さな n であれば単純な再帰でも十分ですが、パフォーマンスを重視する場合は、メモ化による動的計画法を採用するのがおすすめです。