Tech カテゴリのイメージ
Tech

RecursionError: maximum recursion depth exceeded の原因と直し方[Python]

再帰を書いているとこれに出会う。

RecursionError: maximum recursion depth exceeded

while calling a Python objectやin comparisonが続くこともあるが、意味は同じで、関数の呼び出しが深くなりすぎた状態になる。

Pythonは既定で再帰の深さに1000程度の上限を設けている。これはスタックが溢れてインタプリタごと落ちるのを防ぐための安全装置で、無限再帰を早めに知らせてくれる仕組みでもある。

まず疑うべきは、上限が低いことではなく、止まらない再帰を書いていないかになる。

1. 終了条件がない、または到達しない

いちばん多い原因になる。

def fact(n):
    return n * fact(n - 1)     # 止まらない
def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

終了条件を書いていても、そこに到達しない場合がある。

def countdown(n):
    if n == 0:
        return
    countdown(n - 2)     # 奇数から始めると 0 を通り越す

比較は==ではなく<=にしておくほうが安全になる。浮動小数点を減らしていく再帰では、丸め誤差でぴったり一致しないこともある。

2. プロパティや__getattr__の自己参照

見つけにくいのがこれになる。

class User:
    @property
    def name(self):
        return self.name     # 自分自身を呼んでいる

プロパティの中で同じ名前を読むと、またプロパティが呼ばれる。実体は別名にする。

class User:
    def __init__(self, name):
        self._name = name
    @property
    def name(self):
        return self._name

__getattr__でも同様の罠がある。

class Box:
    def __getattr__(self, key):
        return self.data[key]     # data が未定義だと無限再帰

self.dataが存在しないと__getattr__が呼ばれ、その中でまたself.dataを読む。__init__で先に設定するか、object.__getattribute__を使うか、辞書から直接引く。

class Box:
    def __getattr__(self, key):
        try:
            return self.__dict__["data"][key]
        except KeyError:
            raise AttributeError(key)

__init__の中でself.x = ...としているのに__setattr__を定義している場合も、同じ形で無限再帰になる。

3. データ構造に循環がある

木構造だと思って探索したら、実は循環していたというパターンになる。

def walk(node):
    for child in node.children:
        walk(child)     # 親を子に持つと戻ってくる

訪問済みを記録すれば止まる。

def walk(node, seen=None):
    if seen is None:
        seen = set()
    if id(node) in seen:
        return
    seen.add(id(node))
    for child in node.children:
        walk(child, seen)

JSONの循環参照や、相互に参照しあうORMのオブジェクトでも起きる。

4. 本当に深いだけの場合

無限ではなく、単に深い場合もある。連結リストを再帰でたどる、深い木を処理する、といった状況になる。

上限を上げること自体はできる。

import sys
sys.setrecursionlimit(10000)

ただしこれは最後の手段になる。Pythonの再帰はCのスタックを消費するので、上げすぎるとRecursionErrorではなくセグメンテーション違反でプロセスごと落ちる。エラーで止まるほうがまだ扱いやすい。

深さが読めるなら少し上げる程度にとどめ、読めないなら反復に書き換えたほうがいい。

5. 反復に書き換える

多くの再帰は明示的なスタックで置き換えられる。

def walk(root):
    stack = [root]
    seen = set()
    while stack:
        node = stack.pop()
        if id(node) in seen:
            continue
        seen.add(id(node))
        stack.extend(node.children)

深さ優先ならリスト、幅優先ならcollections.dequeを使う。スタックが自前になるので、深さはメモリが許すかぎり伸ばせる。

単純な累積計算なら、そもそもループで書ける。

def fact(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r

なおPythonは末尾再帰の最適化をしないので、末尾呼び出しの形にしても深さは減らない。

どこで回っているか調べる

原因が読めないときは、traceback の繰り返し部分を見る。同じ関数名が延々と並んでいれば、その関数が犯人になる。

現在の深さを確認する手もある。

import sys
def f(n):
    if len(sys._current_frames()) and n % 100 == 0:
        print(n, sys.getrecursionlimit())
    return f(n + 1)

もっと簡単なのは、引数を毎回出して減っているか確かめることになる。同じ値が続いていれば、終了条件に近づいていない。

📘 再帰と反復の書き分けを整理するなら、独習Python。

まとめ

・既定の上限はおよそ1000。まず疑うべきは上限ではなく止まらない再帰のほう
・終了条件の書き忘れと、条件に到達しない減らし方が最頻の原因。比較は<=にする
・プロパティや__getattr__の中で同じ名前を読むと無限再帰になる。実体は別名にする
・循環のあるデータ構造は、訪問済み集合を持たせて止める
・setrecursionlimitは最後の手段。上げすぎるとプロセスごと落ちる
・本質的な対処は明示的なスタックによる反復への書き換え

※本記事にはアフィリエイト広告を含みます。

関連記事