7

数か月前の冗談として、私の同僚は、次の指数アルゴリズムを使用してフィボナッチ数を計算することにより、「宇宙の熱死を加速する」ことを試みました。

int Fib(int n)
{
    if (n <= 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

これはC#でスタックオーバーフローを引き起こさないのですか? あきらめる前になんとか Fib(52) にたどり着きました (そして Fib(51) には何時間もかかりました)。CLR はデフォルトでスタックに 1M しか割り当てないため、これはスタック オーバーフローを引き起こすほどスタックを激しく叩くと思います。また、これは末尾再帰にも適していないと確信しています。

4

2 に答える 2

21

再帰呼び出しは同時には計算されませんが、順番に計算されます。つまり、Fib(n - 2)後で計算されますFib(n - 1)(またはその逆)。これは、2^n再帰呼び出しを作成してもn、同時にアクティブになるのは 2 つだけであることを意味します。したがって 、のスタックフレームFib(52)用のスペースのみが必要になります。これは、52目立っFibたスタックスペースを必要としません。

于 2013-03-07T20:08:08.423 に答える
2

単純な Fibonacci 実装は、実際には多数の関数呼び出しを生成しますが (実際には結果に等しい)、あまり深く再帰することはありません。再帰の最大深さは ですn。

于 2013-03-07T20:09:13.147 に答える