階乗はどのように計算されますか？

Question

は階乗を計算する関数（n）が存在すると言う

ない（7）7

1〜Nのそれぞれについて7関数オブジェクトを作成し、それらの値を使用する要因要因のために（これまで必要（8 ）と同様の階乗（7）* 8）

Answer 1

それは言語と言語の実装に依存します。

多くの関数型言語（たとえばHaskell）では、関数は何も変更しないことが保証されています。値を返すだけです。この副作用の欠如により、言語は関数呼び出しの結果を覚えているか、キャッシュしているか、または「メモする」ことができます。

あまり洗練されていない言語では、7つの異なる関数呼び出しフレームがスタックに配置され、ポップオフされる可能性があります。

多くの関数型言語で正しく書かれた階乗関数も末尾再帰型です。その場合、言語は、関数の一番下から上にジャンプして、別の関数呼び出しを作成しないようにすることもできます。この場合、言語は再帰関数を "フリー"のループにしています。

Answer 2

できます。 memoizationのように聞こえるのは、後で計算を高速化するために以前の結果を保存するということです。たとえば、9！を計算すると、1の値を保存することができます。 .. 9！、そしてあなたが8を求められたら！後で保存された値を返すことができます。同様に、10！を求められたら、10 × 9を計算することができます。早く。

事は、ストレージの多くを使用して終了することができますのnの値が大きいために、こんなに早くその階乗（nは）成長しているので、時空間の貿易は価値がないかもしれません。

メモオンを効果的に使用できるもう1つの機能は、フィボナッチ数を計算することです。

Answer 3

それはあなたが再帰的な階乗関数について話しているように聞こえる、依存：

int factorial(int n) { 
    return n>=1 ? n * factorial(n-1) : 1; 
} 

この関数は、自分自身を呼び出しますrecursively与え階乗（n）を計算するのに必要な回数を。ほとんどすべての再帰関数は、連続した結果を蓄積するために、スタックを使用することによって反復解法に変換することができ

...

int factorial(int n) { 
    int accu = 1; 
    int i; 
    for(i = 1; i <= n; i++) { 
     accu *= i; 
    } 
    return accu; 
}