5

Code Complete 2からの引用、

int Factorial( int number ) {
   if ( number == 1 ) {
      return 1;
   }
   else {
      return number * Factorial( number - 1 );
   }
}

遅く[1]、 ランタイム メモリの使用を予測不可能にする[2]ことに加えて、このルーチンの再帰バージョンは、次の反復バージョンよりも理解しにくいものです。

int Factorial( int number ) {
   int intermediateResult = 1;
   for ( int factor = 2; factor <= number; factor++ ) {
      intermediateResult = intermediateResult * factor;
   }
   return intermediateResult;
}

遅い部分は、不要な関数呼び出しのオーバーヘッドが原因だと思います。

しかし、再帰によってランタイム メモリの使用が予測不能になるのはなぜでしょうか。

どのくらいのメモリが必要になるかを常に予測することはできませんか (再帰がいつ終了するかはわかっています)。反復の場合と同じくらい予測不可能になると思いますが、それ以上ではありません。

4

3 に答える 3

3

再帰的なメソッドは自分自身を繰り返し呼び出すため、大量のスタック メモリが必要です。スタックには制限があるため、スタックメモリを超えるとエラーが発生します。

于 2010-11-02T18:25:21.097 に答える
1

どのくらいのメモリが必要になるかを常に予測することはできませんか (再帰がいつ終了するかはわかっています)。反復の場合と同じくらい予測不可能になると思いますが、それ以上ではありません。

いいえ、一般的なケースではありません。詳細な背景については、停止の問題に関する説明を参照してください。ここで、そこに投稿された問題の 1 つの再帰バージョンを次に示します。

void u(int x) {
    if (x != 1) {
        u((x % 2 == 0) ? x/2 : 3*x+1);
    }
}

末尾再帰ですらあります。これが正常に終了するかどうかさえ予測できない場合、必要なメモリ量をどのように予測できますか?

于 2010-11-04T02:09:28.730 に答える
0

再帰レベルが深くなりすぎると、コール スタックが爆発し、その過程で大量のメモリが消費されます。これnumberは、「十分に大きい」値である場合に発生する可能性があります。これより悪いことはできますか？はい、関数がすべての再帰呼び出しでより多くのオブジェクトを割り当てる場合。

于 2010-11-02T18:36:04.310 に答える