再帰の仕組み | 再帰関数 | Python本格超入門

再帰の仕組み

再帰とは、関数が自分自身を呼び出すことです。再帰関数は、特定の条件を満たすまで自己呼び出しを繰り返し、問題を小さくして解決するアルゴリズムを実現します。本記事では、再帰の基本的な仕組みとその使い方について解説します。

再帰の基本構造

再帰関数には次の2つの重要な要素があります。

• 基本部分（基底条件）: 再帰を終了させる条件。無限ループを防ぐために必要です。
• 再帰部分: 関数が自分自身を呼び出す部分です。

再帰関数の基本的な例として、階乗を計算する関数を見てみましょう。

# 再帰を使った階乗計算
def factorial(n):
    if n == 0:
        return 1  # 基底条件
    else:
        return n * factorial(n - 1)  # 再帰部分

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

この例では、nが0に達すると関数は1を返し、それ以上の再帰は行われません。n > 0の場合、factorial関数は自分自身を呼び出し、再帰的に計算が進行します。

再帰の流れ

再帰がどのように動作するか、ステップごとに階乗の計算を追ってみます。factorial(5)を呼び出した場合、次のように計算が行われます。

1. factorial(5)を呼び出す → 5 * factorial(4)
2. factorial(4)を呼び出す → 4 * factorial(3)
3. factorial(3)を呼び出す → 3 * factorial(2)
4. factorial(2)を呼び出す → 2 * factorial(1)
5. factorial(1)を呼び出す → 1 * factorial(0)
6. factorial(0)は基底条件に達する → 1

これらのステップを経て、最終的な答えは5 * 4 * 3 * 2 * 1 = 120となります。

再帰を使うメリットとデメリット

注意点: 再帰の深さとスタックオーバーフロー

再帰を使う際には、再帰の深さに注意が必要です。Pythonには再帰の深さに制限があり、再帰が深すぎるとRecursionErrorが発生します。例えば、非常に大きな数で再帰的に階乗を計算しようとすると、次のようなエラーが出ることがあります。

# 深すぎる再帰によるエラー
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(1000))  # RecursionError: maximum recursion depth exceeded
    

このエラーを回避するには、sys.setrecursionlimit()を使って再帰の深さを調整するか、再帰をループに置き換えることが推奨されます。

再帰の代替方法: ループによる実装

再帰は便利ですが、必ずしも必要ではない場合もあります。例えば、階乗計算をループで実装することも可能です。以下は、ループを使った階乗計算の例です。

# ループを使った階乗計算
def factorial_loop(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

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

このように、ループを使うことで再帰を避け、メモリの消費を抑えることができます。

まとめ

再帰は強力なツールであり、特に再帰的な問題を解決する際に役立ちます。しかし、再帰を使用する際は、基底条件や再帰の深さに注意する必要があります。場合によっては、ループによる実装が再帰よりも効率的で安全な場合もあるため、適切な方法を選択することが重要です。