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

Question

factorial（n）を計算する関数があるとします

factorial（7）は、1から7までのnごとに7つの関数オブジェクトを作成します

必要に応じてこれらの値を使用します（factorial（7）* 8のようにfactorial（8）の場合）

Answer 1

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

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

それほど洗練されていない言語では、7つの異なる関数呼び出しフレームがスタックに置かれ、ポップされます。

多くの関数型言語で適切に記述された階乗関数も末尾再帰的です。その場合、言語は、関数の下部から上部に単純にジャンプして、別の関数呼び出しの作成を回避することを選択できます。この場合、言語は再帰関数を「無料」ループに変えています。

Answer 2

場合によっては、再帰的階乗関数について話しているように聞こえます：

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

この関数は、再帰的に計算に必要な回数を呼び出します。与えられた階乗（n）。

ほとんどすべての再帰関数は、スタックを使用して連続した結果を蓄積することにより、反復解に変換できます...

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

Answer 3

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

問題は、factorial（ n ）が非常に速く成長することです。 n の値が大きいと、大量のストレージを使用することになり、時空取引価値がないかもしれません。

メモ化を効果的に使用できる別の関数は、フィボナッチ数の計算です。