再帰関数によるスタックオーバーフロー

Question

初心者からC++プログラミングとコンピュータシステムのアーキテクチャまで、私はまだC++の基礎を学んでいます。昨日、私は再帰関数について読んので、私は自分自身を書くことにした、ここで私が書いたものだ：（非常に基本的な）

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

}

をそして私が行うときに、この：int型ZERO1 = returnZero（4793）;スタックオーバーフローが発生しますが、値4792をパラメータとして渡すと、オーバーフローは発生しません。

理由は何ですか？

Answer 1

あなたのシステムのコールスタックのサイズ制限に達しただけです。何が起きているのですか。何らかの理由で、システムのスタックが小さく、4793の関数呼び出しの深さはかなり小さいです。あなたは再帰的に含めて、関数を呼び出すたび

Answer 2

は、リターンアドレスとは、多くの場合、引数はcall stackにプッシュされています。スタックは有限であるため、再帰が深すぎると最終的にスタック領域がなくなります。私に驚き何

は、それが唯一のスタックをオーバーフローするためにあなたのマシン上で4793回のコールを取ることです。これは非常に小さなスタックです。比較のために、私のコンピュータ上で同じコードを実行するには、プログラムがクラッシュする前に〜100倍の呼び出しが必要です。

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

機能はいくつかのコンパイラは、ジャンプにそれを回すことにより、再帰呼び出しを離れて最適化することができるかもしれない、tail-recursiveであることを考えます。いくつかのコンパイラは、さらにあなたの例がかかる場合があります。最大の最適化のために尋ねられたとき、gcc 4.7.2はに全体の機能を変換：

int returnZero(int anyNumber) { 
    return 0; 
} 

これはまさに2アセンブリ命令を必要とします。

_returnZero: 
     xorl %eax, %eax 
     ret 

かなりきちんと。

Answer 3

スタックのサイズが制限されているため、4792が入ってくるうちに、4793コールをすると制限が発生します。各関数呼び出しは、ハウスキーピングと多分引数のためにスタック上のスペースを使います。

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

Answer 4

私の推測では、4792個のエントリを収まるほど正確に大きいスタックです。明日かその次に、その数字は違うかもしれません。再帰的プログラミングは危険なことがあり、この例では理由を示しています。私たちは再帰がこの深い、あるいは「悪い」事態を起こさないようにしようとします。

Answer 5

どれ「無限」再帰は、それが自然にこの効果を持つことになります小さな（ISH）の数に限定されるものではなく、再帰呼び出しです。制限がどこにあるかは、OS、関数が呼び出される環境（コンパイラ、関数が再帰関数などを呼び出すなど）によって決まります。

再帰関数を呼び出す関数に別の変数、たとえばint x[10];を追加すると、それをクラッシュさせるために必要な数値が変更されます（おそらく約5程度）。

別のコンパイラでコンパイルしてください（または最適化を有効にするなど、別のコンパイラ設定を使用することもできます）。再帰を使用して

Answer 6

、あなたはSuperDigitを達成することができます：

public class SuperDigit 
{ 
    static int sum = 0; 

    int main() 
    { 
     int n = 8596854; 
     cout<<getSum(n); 
    } 

    int getSum(int n){ 
     sum=0; 
     while (n > 0) { 
      int rem; 
      rem = n % 10; 
      sum = sum + rem; 
      n = n/10; 
      getSum(n); 
     } 
     return sum; 
    } 
}