3

フィボナッチを計算する2 つの関数がfib1あります。fib2

def fib1(n):
    if n < 2:
        return 1
    else:
        return fib1(n-1) + fib1(n-2)

def fib2(n):
    def fib2h(s, c, n):
        if n < 1:
            return s
        else:
            return fib2h(c, s + c, n-1)
    return fib2h(1, 1, n)

fib2再帰制限を爆破するまで問題なく動作します。正しく理解すれば、Python は末尾再帰を最適化しません。それは私には問題ありません。

fib1の値が非常に小さい場合でも、減速し始めて停止しますn。なぜそれが起こっているのですか？遅くなる前に再帰制限に達しないのはなぜですか?

4

3 に答える 3

6

基本的に、nの同じ値に対してfib1を何度も計算することにより、多くの時間を無駄にしています。このような機能を簡単にメモ化できます

def fib1(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        memo[n] = 1
    else:
        memo[n] =  fib1(n-1) + fib1(n-2)
    return memo[n]

デフォルトの引数として空のdictを使用していることに気付くでしょう。すべての関数呼び出しのデフォルトとして同じdictが使用されるため、これは通常は悪い考えです。

ここでは、それを使用して、計算した各結果をメモ化することで、それを利用しています。

n < 2テストの必要性を回避するために、メモを0と1でプライミングすることもできます

def fib1(n, memo={0: 1, 1: 1}):
    if n in memo:
        return memo[n]
    else:
        memo[n] =  fib1(n-1) + fib1(n-2)
    return memo[n]

になります

def fib1(n, memo={0: 1, 1: 1}):
    return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2))
于 2012-10-11T00:28:45.547 に答える
5

あなたの問題はPythonではなく、あなたのアルゴリズムです。ツリー再帰fib1の良い例です。この特定のアルゴリズムが（〜 ）であるという証拠をstackoverflowで見つけることができます。θ(1.6n)

n=30（どうやらコメントから）約3分の1秒かかります。計算時間がに拡大すると、約210万年かかる1.6^nと予想されます。n=100

于 2012-10-11T00:12:55.193 に答える
2

それぞれの再帰ツリーについて考えてみてください。2番目のバージョンは、関数呼び出しのパラメーター計算で追加が行われる再帰の単一ブランチであり、その後、バックアップされた値を返します。お気づきのとおり、Pythonは末尾再帰の最適化を必要としませんが、末尾呼び出しの最適化がインタープリターの一部である場合は、末尾再帰の最適化もトリガーされる可能性があります。

一方、最初のバージョンでは、各レベルで2つの再帰ブランチが必要です。したがって、関数の潜在的な実行の数はかなり急増します。それだけでなく、ほとんどの作業が2回繰り返されます。考えてみてください。fib1(n-1)最終的には再度呼び出します。これは、最初の呼び出しフレームの参照ポイントからfib1(n-1)呼び出すのと同じです。fib1(n-2)しかし、その値が計算された後、それを再びの値に追加する必要がありますfib1(n-2)！そのため、作業は不必要に何度も複製されます。

于 2012-10-11T00:09:48.613 に答える