Pythonの再帰関数を解説！フィボナッチ数列の実装例も紹介

プログラミングにおいて、再帰関数は重要な概念の一つです。再帰を適切に使うことで、複雑な問題をシンプルに記述でき、コードの可読性を高めることが可能になります。本記事では、Pythonを使って再帰関数の基本構造を学びながら、フィボナッチ数列という題材を通じて、その仕組みと注意点を丁寧に解説していきます。

再帰関数は自分自身を呼び出す関数

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

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

フィボナッチ数列は2つの項の和から求める

フィボナッチ数列は、以下のような規則で構成される無限数列です。

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

この数列は、第0項を0、第1項を1と定義し、それ以降の各項は「直前の2つの項の和」として導出されます。一般的には、以下のような漸化式によって表現されます。

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

このシンプルな構造にもかかわらず、フィボナッチ数列は数学的に多くの興味深い性質を持っています。例えば、ウサギの繁殖モデルや黄金比との関連性など、様々な文脈で登場することから、再帰の学習教材としても適しています。

Pythonで再帰関数を実装する

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

1
def recursive_function(param):
2
    if 条件:  # 終了条件
3
        return 結果
4
    else:
5
        return recursive_function(新しいparam)

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

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

1
def countdown(n):
2
    if n == 0:  # 終了条件
3
        print("終了！")
4
    else:
5
        print(n)
6
        countdown(n - 1)
7

8
countdown(5)

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

1
$ python recursion_ex01.py
2
5
3
4
4
3
5
2
6
1
7
終了！

Pythonで階乗の計算をする

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

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

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

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

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

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

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

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

1
$ python recursion_ex02.py
2
120

Pythonでフィボナッチ数列の計算をする

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

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

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

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

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

1
def fibonacci(n):
2
    if n == 0:
3
        return 0
4
    elif n == 1:
5
        return 1
6
    return fibonacci(n - 1) + fibonacci(n - 2)
7

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

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

1
$ python example.py
2
8

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

再帰関数のメリット

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

再帰関数のデメリット

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

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

終了条件を明確にする

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

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

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

1
from functools import lru_cache
2

3
@lru_cache(maxsize=None)
4
def fibonacci(n):
5
    if n == 0:
6
        return 0
7
    elif n == 1:
8
        return 1
9
    return fibonacci(n - 1) + fibonacci(n - 2)
10

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

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

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

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

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

1
def fibonacci_iterative(n):
2
    a, b = 0, 1
3
    for _ in range(n):
4
        a, b = b, a + b
5
    return a
6

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

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

再帰関数まとめ

記事で紹介した主なポイントは以下の通りです。

• 再帰関数は自分自身を呼び出すことで問題を分割し、シンプルに問題を解決できる。
• 再帰関数は同じ計算を繰り返すことで時間計算量が急増し、スタックオーバーフローのリスクもあるので注意が必要。
• functools.lru_cacheで結果をキャッシュし、処理を高速化できる。
• 再帰を使わず、ループによって効率的にフィボナッチ数列を求めることもできる。

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

Pythonユーザにお勧めの本

スッキリわかるPython入門 第2版 スッキリわかるシリーズ

独習Python

Python1年生 第2版 体験してわかる！会話でまなべる！プログラミングのしくみ

スポンサーリンク