【Python】第3章第6回：再帰関数の基礎と注意点

本記事では、Pythonにおける再帰関数の基本的な仕組みと使用時の注意点について解説します。再帰関数を理解することで、複雑なアルゴリズムを簡潔に実装できるようになります。

0. 記事の概要

この記事を読むメリット

• 再帰関数の基本を理解：再帰的なアルゴリズムの構築が可能になります。
• 効率的なコード記述：再帰を用いてシンプルなコードを書けるようになります。
• 応用力を向上：再帰関数を使った実践的な例を学べます。

この記事で学べること

• 再帰関数の基本的な仕組み
• 再帰関数を使った実践例
• 無限再帰を防ぐための注意点

1. 再帰関数の基本

1.1 再帰関数とは？

再帰関数とは、関数内部で自分自身を呼び出す関数のことです。再帰関数を使用することで、繰り返し処理を簡潔に記述できます。

# 再帰関数の基本例：階乗を計算
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

result = factorial(5)
print(f"5の階乗: {result}")

動作解説

1. factorial(5)が呼び出され、nが0になるまで再帰的に呼び出しが繰り返されます。
2. 再帰の終了条件（ベースケース）として、n == 0の場合は1を返します。
3. 再帰呼び出しが終了すると、結果が逆順に計算され、最終的な結果を返します。

2. 再帰関数の実践例

2.1 フィボナッチ数列の生成

再帰関数を使ってフィボナッチ数列を生成するプログラムを作成します。

# 再帰関数でフィボナッチ数列を生成
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(f"フィボナッチ({i}): {fibonacci(i)}")

動作解説

1. fibonacci(n)が呼び出され、nが1以下になるまで再帰的に処理を繰り返します。
2. fibonacci(n - 1)とfibonacci(n - 2)を計算し、その和を返します。

2.2 再帰を用いた二分探索

再帰関数を使って、ソートされたリストから特定の値を検索する二分探索アルゴリズムを実装します。

# 再帰関数で二分探索
def binary_search(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

sorted_list = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search(sorted_list, target, 0, len(sorted_list) - 1)
print(f"ターゲットのインデックス: {result}")

動作解説

1. binary_searchが呼び出され、リストの中央の要素を調べます。
2. ターゲットが中央の要素と一致する場合、そのインデックスを返します。
3. 一致しない場合、探索範囲を半分に絞って再帰的に処理を続けます。

3. 再帰関数を使用する際の注意点

3.1 無限再帰を防ぐ

再帰関数には必ず終了条件を設ける必要があります。終了条件がない場合、無限再帰が発生し、プログラムがクラッシュする原因となります。

3.2 スタックオーバーフローに注意

再帰関数はスタックを使用して実行されるため、再帰の深さが深すぎるとメモリ不足（スタックオーバーフロー）になることがあります。Pythonでは再帰の深さがデフォルトで1000回に制限されています。

4. 練習問題

以下の課題に挑戦してみましょう。

1. 再帰関数を使ってリスト内の最大値を見つける関数を作成してください。
2. 再帰を使って文字列を逆順にする関数を作成してください。

5. 練習問題の解答と解説

問1の解答例

# 再帰関数でリスト内の最大値を見つける
def find_max(arr):
    if len(arr) == 1:
        return arr[0]
    return max(arr[0], find_max(arr[1:]))

numbers = [1, 5, 3, 9, 2]
print(f"最大値: {find_max(numbers)}")

問2の解答例

# 再帰関数で文字列を逆順にする
def reverse_string(s):
    if len(s) == 0:
        return ""
    return s[-1] + reverse_string(s[:-1])

text = "Python"
print(f"逆順: {reverse_string(text)}")

6. まとめ

再帰関数は、複雑な問題をシンプルに解決する強力なツールです。ただし、無限再帰やスタックオーバーフローに注意して使用してください。