【Python】再帰関数をフィボナッチ数列の実装例で解説！

1. 再帰関数とは？

再帰関数とは、関数の中で自分自身を呼び出す関数のことを指します。
プログラミングにおいて、再帰は複雑な問題を単純な形に分割して解くための手法です。
再帰を使うことで、ループでは表現しづらい問題を簡潔に書くことが可能です。

例えば、数学的な概念（階乗やフィボナッチ数列など）や、データ構造（木構造の探索など）の操作で利用されます。

2. 再帰関数の基本構造

Pythonにおける再帰関数は、次のような構造を持ちます。

def recursive_function(param):
    if 条件:  # 終了条件
        return 結果
    else:
        return recursive_function(新しいparam)

再帰関数の重要な要素は終了条件です。
終了条件がないと再帰が無限に続き、プログラムがクラッシュ（スタックオーバーフロー）してしまいます。

例えば、数を1ずつ減らしていき0になったら終了する再帰関数は以下のように記述します。

def countdown(n):
    if n == 0:  # 終了条件
        print("終了！")
    else:
        print(n)
        countdown(n - 1)

countdown(5)

このコードは、5から0までのカウントダウンを表示します。

3. 再帰関数の実例

階乗の計算

階乗（n!）は、次の式で定義されます。

n! = n × (n-1) × (n-2) × ... × 1

例えば、5の階乗は次のように計算されます。

5! = 5 × 4 × 3 × 2 × 1 = 120

再帰関数を用いて階乗を計算するコードは以下の通りです。

def factorial(n):
    if n == 0 or n == 1:  # 終了条件
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 出力: 120

このコードでは、関数factorialが自分自身を呼び出し、nが1または0になるまで計算を繰り返します。

フィボナッチ数列

フィボナッチ数列とは、次のように定義される数列です。

F(n) = F(n-1) + F(n-2)  (n >= 2)
F(0) = 0, F(1) = 1

具体例として、最初の6項は次の通りです。

0, 1, 1, 2, 3, 5, 8

再帰関数を用いてフィボナッチ数列を計算する方法は以下の通りです。

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # 出力: 8

この実装では、再帰的に数列の前の2項を計算し、6項目を返します。

4. 再帰関数のメリットとデメリット

メリット

1. コードの簡潔さ: 再帰を使うことで、問題を直感的かつ簡潔に表現できます。
   • 例: フィボナッチ数列や階乗の計算。
2. 木構造やグラフの探索に適している: 再帰は分岐を持つ問題（例: 深さ優先探索）を効率的に解く手段です。

デメリット

1. パフォーマンスが低下しやすい: 再帰関数は関数呼び出しごとにメモリを消費するため、大きな入力に対して非効率的になる場合があります。
2. スタックオーバーフローのリスク: 終了条件が設定されていない場合や、計算が深くなりすぎた場合にエラーが発生します。
3. デバッグが難しい: 再帰の各ステップを追跡するのは、ループに比べて複雑です。

5. 再帰関数を使う際の注意点

1. 終了条件を明確にする

再帰関数を正しく動作させるためには、必ず終了条件を設ける必要があります。終了条件がないと、無限ループに陥りプログラムがクラッシュします。

2. メモ化（キャッシュ）を利用する

再帰関数は同じ計算を何度も繰り返すことがあります。この問題を解決するために、計算結果をキャッシュする方法（メモ化）が有効です。 Pythonでは、functools.lru_cacheを使うことで簡単に実現できます。

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(50))  # 出力: 12586269025

この方法では、すでに計算した値をキャッシュし、パフォーマンスを大幅に向上させます。

3. ループと比較して適切な手法を選ぶ

再帰関数はシンプルですが、すべての場面で最適とは限りません。特に計算量が多い場合、ループ処理の方が効率的なことがあります。

例として、フィボナッチ数列をループで計算するコードは以下のようになります。

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_iterative(50))  # 出力: 12586269025

この方法では、再帰を使わないためメモリ使用量を削減できます。

6. まとめ

Pythonの再帰関数は、数学的な問題や木構造の探索など、特定の問題を解決することができます。
しかし、パフォーマンスやメモリ消費に注意し、適切な設計を心がけることが重要です。
メモ化やループ処理を適宜組み合わせ、効率的で読みやすいコードを目指しましょう。

スポンサーリンク