18

私はC++の初心者です。昨日、再帰関数について読んだので、自分で書くことにしました。ここに私が書いたものがあります：

int returnZero(int anyNumber) {
    if(anyNumber == 0)
        return 0;
    else  {
        anyNumber--;
        return returnZero(anyNumber);
    }
}

これを行うと: int zero1 = returnZero(4793);、スタック オーバーフローが発生します。ただし、値 4792 を引数として渡すと、オーバーフローは発生しません。

理由についてのアイデアはありますか？

4

6 に答える 6

41

再帰を含め、関数を呼び出すたびに、戻りアドレスと多くの場合引数が呼び出しスタックにプッシュされます。スタックは有限であるため、再帰が深すぎると、最終的にスタック領域が不足します。

驚いたことに、あなたのマシンでは 4793 回の呼び出しでスタックがオーバーフローしました。これはかなり小さなスタックです。比較すると、私のコンピューターで同じコードを実行すると、プログラムがクラッシュするまでに最大 100 倍の呼び出しが必要になります。

スタックのサイズは構成可能です。Unix では、コマンドはulimit -s.

関数が末尾再帰であることを考えると、一部のコンパイラは、再帰呼び出しをジャンプに変えることで最適化できる場合があります。一部のコンパイラは、あなたの例をさらに進める可能性があります。最大の最適化を求められた場合、gcc 4.7.2関数全体を次のように変換します。

int returnZero(int anyNumber) {
  return 0;
}

これには、正確に 2 つの組み立て手順が必要です。

_returnZero:
        xorl    %eax, %eax
        ret

かなりきれい。

于 2013-04-12T16:24:36.643 に答える
3

システムの呼び出しスタックのサイズ制限に達しただけです。それが起こっていることです。何らかの理由で、システムのスタックは小さく、4793 の関数呼び出しの深さはかなり小さいです。

于 2013-04-12T16:24:13.263 に答える
2

スタックはサイズが限られているため、4793コールを行うと、制限に達しているのに4792下に来るだけです。各関数呼び出しは、ハウスキーピングとおそらく引数のためにスタック上のスペースを使用します。

このページでは、再帰関数呼び出し中にスタックがどのように見えるかの例を示します。

于 2013-04-12T16:24:37.507 に答える
1

私の推測では、スタックは 4792 エントリにちょうど収まる大きさです - 今日。明日か明後日、その数は違うかもしれません。再帰的プログラミングは危険な場合があり、この例はその理由を示しています。再帰がこれほど深くならないようにしています。そうしないと、「悪い」ことが起こる可能性があります。

于 2013-04-12T16:25:06.293 に答える
1

「無限の」再帰、つまり、自然に小さな（っぽい）数に制限されない再帰呼び出しは、この効果があります。制限が正確にどこに行くかは、OS、関数が呼び出される環境 (コンパイラ、再帰関数を呼び出す関数など) によって異なります。

たとえばint x[10];、再帰関数を呼び出す関数に別の変数を追加すると、クラッシュするのに必要な数が変わります (おそらく約 5 程度)。

別のコンパイラでコンパイルすると (最適化がオンになっているなどの別のコンパイラ設定でも)、おそらく再び変更されるでしょう。

于 2013-04-12T16:29:07.830 に答える