再帰とは、関数が自分を呼んで問題を小さくする仕組み

再帰はどこで崩れるのか

再帰は、止まる条件が抜けたときと、入れ子が深すぎるときに崩れます。どちらもスタックが上限に届き、Python では RecursionError という例外で止まります。

止まる条件が抜けると、上限まで積み上がる

止まる条件の無い再帰は、積むだけで一度も降ろせません。Python は呼び出しの深さに上限を持ち、超えると RecursionError を出します。公式文書は、この上限を、無限の再帰で C のスタックがあふれて Python ごと落ちるのを防ぐ物と説明しています。

上限は sys.getrecursionlimit() で読み、sys.setrecursionlimit() で変えます。手元の CPython 3.14 では、何も変えずに読むと 1000 でした。ブラウザの Python では値が違うことがあります。

次のコードは、止まる条件の無い関数を上限 200 と 400 で動かし、潜れた深さを比べます。

200 RecursionError
400 RecursionError
深さの差 200
RuntimeError の仲間 True

どちらも RecursionError で止まり、上限を 200 増やすと、潜れた深さもちょうど 200 増えました。止まる深さを決めているのは上限の値で、上限を上げても、止まる条件が無ければ遅く止まるだけです。

RecursionError は RuntimeError の子のクラスで、公式文書によると Python 3.5 より前はただの RuntimeError でした。公式文書は、上げられる上限は環境で違い、高すぎると Python が落ちることがあるとも書いています。

入れ子が深すぎる入力は、ループに書き換える

止まる条件が正しくても、入力の入れ子が上限より深ければ再帰は止まります。外から来るデータの深さは、こちらで決められません。

再帰は、呼び出しのスタックの代わりに自前のスタック (リスト) を持てば、ループに書き換えられます。次のコードは、7 を 2 万重のリストで包んだ入力を、再帰の flat とループの flat_loop で平らにします。

再帰 RecursionError
ループ [7]
[1, 2, 3, 4, 5]

再帰の flat は途中で上限に届き、flat_loop は最後まで処理しました。まだ見ていない物を todo に積んで 1 つずつ取り出すので、積む場所が上限のあるスタックからふつうのリストに変わっただけです。中身を逆順に積むのは、後から積んだ物が先に出るからで、こうすると左から順に出ます。

階乗のように自分を 1 回だけ呼ぶ形なら、スタックも要りません。

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

自分を 2 回以上呼ぶ再帰は、同じ小さな問題を何度も解き直すことがあります。フィボナッチ数の素直な再帰がその例で、呼ぶ回数が急に増えます。この遅さと直し方は 2-9 の動的計画法の回で扱います。