Pythonの再帰はなぜ高いのか、そしてどうすればいいのか？

質問

997をモジュロとするいくつかのフィボナッチ数を計算したいとします。

に対して n=500 をC++で実行することができます。

#include <iostream>
#include <array>

std::array<int, 2> fib(unsigned n) {
    if (!n)
        return {1, 1};
    auto x = fib(n - 1);
    return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997};
}

int main() {
    std::cout << fib(500)[0];
}

そしてPythonでは

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    print(fib(500)[0])

どちらも問題なく996という答えを見つけることができます。出力サイズを合理的に保つためにモジュロをとり、指数的な分岐を避けるためにペアを使用しています。

に対して n=5000 に対して、C++のコードは783を出力しますが、Pythonは文句を言います。

RecursionError: maximum recursion depth exceeded in comparison

2行ほど追加すると

import sys

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    sys.setrecursionlimit(5000)
    print(fib(5000)[0])

とすれば、Pythonも正しい答えを出すでしょう。

については n=50000 C++はミリ秒以内に151の答えを見つけますが、Pythonはクラッシュします（少なくとも私のマシンでは）。

なぜ C++ では再帰呼び出しがそんなに安いのでしょうか？Pythonのコンパイラーをどうにかして、再帰をより受け入れるように変更できないでしょうか？

もちろん、1つの解決策は再帰を反復に置き換えることです。フィボナッチ数については、これは簡単です。しかし、これは初期条件と終端条件を入れ替えることになり、後者は多くの問題で厄介です（例：アルファベータプルーニングなど）。ですから一般的に、これはプログラマーの側で多くのハードワークが必要になります。

どのように解決するのか？

解決方法はトランポリンです。再帰的な関数は、別の関数を呼び出す代わりに、適切な引数でその呼び出しを行う関数を返します。1レベル上のループがあり、最終的な結果が得られるまで、それらの関数をすべてループで呼び出すのです。おそらくうまく説明できていないでしょう。オンラインでもっとうまく説明している資料が見つかるでしょう。

ポイントは、再帰を反復に変換していることです。

ポイントは、再帰を反復に変換していることです。

実装は以下のようになります。私はペアを分割して x を a と b を追加し、分かりやすくしました。次に、再帰的な関数を、以下のものを追跡するバージョンに変換しました。 a と b を引数にとり、末尾再帰的にする。

def fib_acc(n, a, b):
    if n == 1:
        return (a, b)
    return lambda: fib_acc(n - 1, (a+b) % 997, (a+2*b) % 997)

def fib(n):
    x = fib_acc(n, 1, 2)
    while callable(x):
        x = x()
    return x

if __name__=='__main__':
    print(fib(50000)[0])