Python RecursionError: maximum recursion depth exceeded の原因と解決方法【再帰処理の落とし穴と実践的デバッグ】

RecursionError: maximum recursion depth exceeded とは

Pythonで再帰関数を扱う際、「RecursionError: maximum recursion depth exceeded」というエラーに遭遇することは少なくありません。これは、再帰呼び出しが指定された回数を超えて行われたことを示すエラーです。多くの場合、再帰の終了条件が正しく定義されていないか、非常に深い再帰が必要な処理で発生します。

エラーの発生パターン

このエラーは主に以下のようなケースで発生します。

パターン1: 1. 再帰の終了条件が不足している、または誤っている

def infinite_recursion(n):
    # 終了条件がないため、nがどんな値でも無限に再帰する
    return infinite_recursion(n + 1)

infinite_recursion(0)

最も一般的な原因は、再帰関数の終了条件（ベースケース）が定義されていないか、誤っている場合です。これにより、関数が無限に自身を呼び出し続け、Pythonの呼び出しスタックが限界に達してRecursionErrorが発生します。

def factorial(n):
    if n == 0:  # 終了条件（ベースケース）
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5)) # 120

パターン2: 2. 再帰呼び出し時の引数が誤っている

def process_list(data):
    if not data: # リストが空であれば終了
        return []
    # 常に同じリストを渡しているため、リストが空にならない
    return [data[0]] + process_list(data)

process_list([1, 2, 3])

再帰呼び出しの際に渡す引数が適切に更新されず、ベースケースに到達しない場合があります。上記例では、常に同じリストを引数として渡しているため、dataが空になることがなく、再帰が終了しません。

def process_list(data):
    if not data:
        return []
    # リストの先頭要素を取り除いた残りを再帰呼び出しの引数として渡す
    return [data[0] * 2] + process_list(data[1:])

print(process_list([1, 2, 3])) # [2, 4, 6]

パターン3: 3. 大規模なデータ構造や深いツリー構造の処理

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children is not None else []

def get_depth(node):
    if not node.children:
        return 1
    # 非常に深いツリー構造ではデフォルトの再帰深度を超える
    return 1 + max(get_depth(child) for child in node.children)

# 意図的に深いツリーを作成
root = Node(0)
current = root
for i in range(1001):
    new_node = Node(i+1)
    current.children.append(new_node)
    current = new_node

# print(get_depth(root)) # RecursionErrorが発生する可能性が高い

アルゴリズム自体は正しくても、処理するデータ構造が非常に深く、Pythonのデフォルトの再帰深度制限（通常1000）を超える場合に発生します。ファイルシステムの探索やXML/JSONの深いネスト構造の解析などで見られます。

import sys

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children is not None else []

def get_depth_iterative(node):
    # 再帰を使わず、反復処理で深さを計算する
    max_depth = 0
    stack = [(node, 1)] # (ノード, 現在の深さ)
    while stack:
        current_node, current_depth = stack.pop()
        max_depth = max(max_depth, current_depth)
        for child in current_node.children:
            stack.append((child, current_depth + 1))
    return max_depth

# 意図的に深いツリーを作成 (上記と同じ)
root = Node(0)
current = root
for i in range(1001):
    new_node = Node(i+1)
    current.children.append(new_node)
    current = new_node

# print(get_depth_iterative(root)) # 再帰エラーなく実行可能

根本原因の特定方法

RecursionErrorが発生した場合、まずはエラーメッセージに表示されるスタックトレースを確認し、{marker}どの関数が繰り返し呼び出されているか{/marker}を特定します。特に、再帰の{marker}終了条件や引数の変化{/marker}に注目してコードを追うことが重要です。Pythonのデバッガpdbを使ってステップ実行し、関数の呼び出しの流れや変数の状態を詳細に確認することも有効です。

import sys
import pdb

def buggy_recursive_function(n):
    if n == 5: # 本来はn==0などで終了すべき
        return n
    print(f'Calling with n={n}')
    # pdb.set_trace() # ここでブレークポイントを設定
    return buggy_recursive_function(n + 1)

# デフォルトの再帰深度制限を確認
print(f"Default recursion limit: {sys.getrecursionlimit()}")

try:
    buggy_recursive_function(0)
except RecursionError as e:
    print(f"Caught error: {e}")
    # エラー発生時のスタックトレースを表示
    import traceback
    traceback.print_exc()

防止策とベストプラクティス

再帰エラーの最も確実な予防策は、{marker}再帰関数を反復処理に書き換える{/marker}ことです。特に、再帰深度が深くなることが予測される場合や、パフォーマンスが重要な場面では、反復処理の方が優れています。また、再帰関数を設計する際は、必ず明確な終了条件（ベースケース）を設定し、再帰呼び出しのたびに引数がベースケースに向かって変化することを確認しましょう。

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

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

# print(fibonacci_recursive(10)) # 通常は動くが、大きなnではエラー
print(fibonacci_iterative(1000)) # RecursionErrorを回避し、大きな数でも計算可能

よくある質問（FAQ）

この用語と一緒に知っておきたい用語