PythonでN番目のフィボナッチ数を求める方法｜再帰と動的計画法を解説

この記事では、Pythonを使ってN番目のフィボナッチ数を計算する方法を解説します。

フィボナッチ数とは

フィボナッチ数は、次の漸化式によって定義される数列です。

F_n = F_n-1 + F_n-2

初期値は F₀ = 0、F₁ = 1 となります。したがって、フィボナッチ数列の最初のいくつかの項は以下のようになります。

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

フィボナッチ数を求めるには、大きく分けて「再帰」と「動的計画法」の2つのアプローチがあります。それぞれの実装方法をPythonスクリプトで見ていきましょう。

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

まずは最も直感的な再帰による実装です。関数が自分自身を呼び出すことで、漸化式をそのままコードに反映できます。

サンプルコード

# 再帰によるアプローチ
def Fibonacci(n):
    if n < 0:
        print("フィボナッチ数は計算できません")
    # 第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

このプログラムでは、宣言されたすべての変数のスコープは以下のようになっています。

再帰的なアプローチはシンプルで理解しやすい反面、同じ計算を何度も繰り返すため、nが大きくなると処理時間が指数関数的に増加するという欠点があります。

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

次に紹介するのは動的計画法です。一度計算した結果を配列に保存しておくことで、重複する計算を避け、効率よくフィボナッチ数を求められます。

サンプルコード

# 動的計画法によるアプローチ
Fib_Array = [0, 1]

def fibonacci(n):
    if n < 0:
        print("フィボナッチ数は計算できません")
    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

このプログラムにおける変数のスコープは以下の通りです。

動的計画法では計算済みの値をメモ化して再利用するため、再帰のみの実装と比べて大幅に高速に動作します。大きなnに対しても実用的なパフォーマンスを発揮します。

まとめ

この記事では、Pythonを使ってN番目のフィボナッチ数を計算する2つの方法——再帰と動的計画法——について学びました。小さなnであれば再帰でも十分ですが、効率を重視する場合はメモ化を活用した動的計画法を選ぶのがおすすめです。用途に応じて適切な手法を使い分けましょう。