1. ホーム
  2. パイソン

[解決済み】Pythonは末尾再帰を最適化するか?

2022-04-01 03:31:43

質問

次のようなコードがあるのですが、次のようなエラーで失敗します。

RuntimeError: 最大の再帰的深度を超えました。

末尾再帰最適化(TCO)ができるように書き換えを試みました。TCOが行われていれば、このコードは成功するはずだったのだと思います。

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

PythonはどのようなタイプのTCOもしないと結論づけるべきか、それとも別の定義が必要なのでしょうか?

どのように解決するのですか?

いいえ、これからもありません。 グイド・ヴァン・ロッサム は、適切なトレースバックが可能であることを好みます。

テール再帰性排除 (2009-04-22)

テールコールの最後の言葉 (2009-04-27)

このような変換で再帰を手動で解消することができます。

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500