はじめに
Pythonでは、再帰呼び出し回数の上限が決められています。私の環境だと、1000回が上限となっていました。
>>> import sys
>>> sys.getrecursionlimit()
1000
こちらの上限を超えた再帰呼び出しを行いたい場合に使える方法を紹介します。
方法
こちらの再帰関数を例に説明します。
def factorial(n):
if n < 2:
return 1
return factorial(n - 1) * n
まず、再帰呼び出し箇所の周りを、(yield ～)で囲みます。上記コードの場合、factorial(n - 1)を(yield factorial(n - 1))に変更します。
def factorial(n):
if n < 2:
return 1
return (yield factorial(n - 1)) * n
あとは、以下の関数を用意して、trampoline(factorial(10))のように呼び出すだけです。
def trampoline(f):
stack, ret = [f], None
while stack:
try:
stack.append(stack[-1].send(ret))
ret = None
except StopIteration as e:
stack.pop()
ret = e.value
return ret
原理
トランポリンとジェネレータの組み合わせで実装しています。
トランポリンについては、「トランポリン 再帰」あたりで検索すれば情報が出てきます。関数を直接呼び出すのではなく、いったん呼び出し元に返してから呼び出すことで、再帰呼び出しの回数を増やさないようにするテクニックです。
ジェネレータは、通常yieldで順番に値を生成するのに使いますが、実は外部からsendで値を渡すとyieldの戻り値になる、という機能があります。
あとは、再帰呼び出しするはずだった関数をyieldで呼び出し元に返してから呼び出し、結果が求まったらsendで続きの計算を行うようにしてあげれば、再帰呼び出しの回数を増やさずに再帰を行うことができます。
注意
もとからジェネレータとなっている関数には使用できません。
例外には対応していません。
他の方法との比較
sys.setrecursionlimitを使う
再帰呼び出しの上限を増やします。こちらで事足りる場合はこちらを使うべきです。
ただし、プラットフォームがサポートしている範囲を超えた値を設定するとクラッシュするので、別の方法を検討する必要があります。
sys.setrecursionlimitとresource.setrlimitを使う
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))とすることで、再帰呼び出しの上限をさらに増やせます。ただし環境によっては使用できない場合があります。
再帰をループに書き換える
再帰関数は、ループに書き換えることができます。ただ、見た目が大きく変わるので、後から修正するのが困難になります。汎用の方法については、昔以下のような記事を書いています。
最後に
昔、AtCoderでこちらの問題に引っ掛かっている人を何人か見かけたので、記事にしてみました。一応、AtCoderで使えることは確認しています。余計なことをしているので遅くなりそうですが。
実は、同じことをするライブラリがすでに公開されています。実際に使うなら、こちらの方が良いでしょう。こちらは例外にも対応していますし、末尾再帰を最適化することも可能です。