1

たとえば、教科書のコード（再帰を使用してフィボナッチ問題を解決する）は次のようになります。

cache = {}

def fibo(n):
    if n in cache :
        return cache[n]
    elif n <=2:
        cache[n] = 1
    else:
        cache[n] = fibo(n-1) + fibo(n-2)
    return cache[n]

ただし、関数呼び出しを行うたびにコストがかかるのではないかと心配しています。不要な関数呼び出しを避けるために、教科書が代わりにこのコードを使用しなかったのはなぜですか。

cache = {}

def fibo(n):
    if n <=2:
        cache[n] = 1
    else:
        # to avoid unnecessary function call
        if n-1 in cache:
            f1 = cache[n-1]
        else:
            f1 = fibo(n-1)
        if n-2 in cache:
            f2 = cache[n-2]
        else:
            f2 = fibo(n-2)

        cache[n] = f1 + f2

    return cache[n]

このようにして、実際に呼び出す前に不要な関数呼び出しを回避できます。

とにかく、私の質問は、なぜ教科書の作者は2番目の方法でコードを書かないのですか？

4

1 に答える 1

4

あなたが説明しているのは動的計画法です。配列を使用して、再帰、メモ化のステップを格納しています。反復ごとに複数の再帰呼び出しがあるフィボナッチのようなものでは、動的計画法が実際に推奨される手法です。

教科書がそれが行ったコードを示した理由については、おそらく、著者が一度に多くの概念に立ち入ることなく再帰を示したかったためです。

于 2012-08-04T00:19:16.610 に答える