再帰によるjava.lang.StackOverflowError

Question

私の問題は、再帰を使用すると通常はjava.lang.StackOverflowErrorが発生することです。 私の質問は - 再帰はなぜスタックオーバーフローを引き起こすのですか？それ以上のループは何ですか、スタックオーバーフローを避けるために再帰を使う良い方法はありますか？

これはproblem 107を解決するための試みである、それは彼らの例に適していますが、問題のそれを自己のためのスタック領域が不足します。

//-1 16 12 21 -1 -1 -1 16 -1 -1 17 20 -1 -1 12 -1 -1 28 -1 31 -1 21 17 28 -1 18 19 23 -1 20 -1 18 -1 -1 11 -1 -1 31 19 -1 -1 27 -1 -1 -1 23 11 27 -1 
public class tries 
{ 
    public static int n=7,min=Integer.MAX_VALUE; 
    public static boolean[][] wasHere=new boolean[n][60000]; 
    public static void main(String[] args) 
    { 
     int[] lines=new int[n]; Arrays.fill(lines, -1000); lines[0]=0; 
     int[][] networkMatrix=new int[n][n]; 
     Scanner reader=new Scanner(System.in); 
     int sum=0; 
     for(int k=0; k<n; k++) 
     { 
      for(int r=0; r<n; r++) 
      { 
       networkMatrix[k][r]=reader.nextInt(); 
       if(networkMatrix[k][r]!=-1) sum+=networkMatrix[k][r]; 
       Arrays.fill(wasHere[k], false); 
      } 
     } 
     recursive(lines,networkMatrix,0,0); 
     System.out.println((sum/2)-min); 
    } 
    public static void recursive(int[] lines, int[][] networkMatrix, int row,int lastRow) 
    {  
     wasHere[row][value((int)use.sumArr(lines))]=true; 
     if(min<sum(lines)) return; 
     if(isAllNotMinus1000(lines)) min=sum(lines); 
     int[][] copyOfMatrix=new int[n][n]; 
     int[] copyOfLines; 
     for(int i=0; i<n; i++) 
     { 
      copyOfLines=Arrays.copyOf(lines, lines.length); 
      for(int k=0; k<n; k++) copyOfMatrix[k]=Arrays.copyOf(networkMatrix[k], networkMatrix[k].length); 
      if(i!=0&&copyOfMatrix[i][row]!=0) copyOfLines[i]=copyOfMatrix[i][row]; 
      copyOfMatrix[i][row]=0; copyOfMatrix[row][i]=0; 
      if(networkMatrix[row][i]==-1) continue; 
      if(wasHere[i][value((int)use.sumArr(copyOfLines))]) continue; 
      if(min<sum(copyOfLines)) continue; 
      recursive(copyOfLines,copyOfMatrix,i,row); 
     } 
    } 
    public static boolean isAllNotMinus1000(int[] lines) 
    { 
     for(int i=0; i<lines.length; i++) {if(lines[i]==-1000) return false;} 
     return true; 
    } 
    public static int value(int n) 
    { 
     if(n<0) return (60000+n); 
     return n; 
    } 
    public static int sum(int[] arr) 
    { 
     int sum=0; 
     for(int i=0; i<arr.length; i++) 
     { 
      if(arr[i]==-1000) continue; 
      sum+=arr[i]; 
     } 
     return sum; 
    } 
} 

Answer 1

なぜそんなに多く、各再帰呼び出しスタック上のいくつかの領域を使用するためのループが

を行うよりも、再帰原因のstackoverflowを行います。再帰が深すぎると、スタックの最大許容深度に応じて、StackOverflowになります。

再帰を使用する場合は、非常に注意して、base caseを指定してください。再帰の基本ケースは、再帰が終了する条件であり、スタックは巻き戻しを開始します。これが再帰の主な理由で、エラーStackOverflowが発生します。基本ケースが見つからない場合、無限回帰に入ります。Stackは有限であるため、確かにエラーになります。

Answer 2

正しく使用すると、再帰ではStackOverflowErrorが生成されません。もしそうであれば、あなたの基底ケースはトリガーされておらず、メソッドは自分自身を無期限に呼び出し続けます。完了しないメソッド呼び出しはすべてスタックに残り、最終的にオーバーフローします。

しかし、ループが自分自身でメソッド呼び出しを伴わないので、何もスタック上に蓄積していないとStackOverflowErrorはなりません。

Answer 3

あなたがメソッドを呼び出すたびに、スタックから「フレーム」を消費し、このフレームは、メソッドが戻るまで解放されていない、それはループと同じように発生しません。再帰的な方法は、スタックメモリ空間を排気させる存在しないか、到達不能終了条件と、不明確されたため、ほとんどの場合

Answer 4

は、スタックオーバーフローが発生します。正しく書かれた再帰は、スタックのオーバーフローを引き起こすべきではありません。

しかし、正しく実装されていれば、メソッドがでものスタックオーバーフローを発生させる可能性があります。例えば、

• 急成長（例えば、指数関数的）再帰。例：フィボナッチ関数の素朴な再帰的な実装は
• 最終的にスタック領域が

ボトムラインを枯渇させることになる非常に大きな入力データ、：それはすべて、特定の場合に依存し、それはすることは不可能ですスタックオーバーフローの原因を一般化する。

Answer 5

再帰によってスタックオーバーフローが発生するため、以前の呼び出しはすべてメモリに格納されます。そのため、あなたのメソッドは新しいパラメータで自分自身を呼び出すと、再びそれ自身を呼び出します。これらの呼び出しはすべてスタックアップし、通常はメモリが不足する可能性があります。 ループは結果を通常いくつかの変数に格納し、新しい呼び出しのようなメソッドを呼び出します。呼び出しごとに呼び出し元メソッドが終了し、結果が返されます。

Answer 6

各再帰呼び出しでは、スタック上のいくつかの領域が使用されます（引数、ローカル変数など、その1つの呼び出しに固有のものを格納します）。したがって、あなたがあまりにも多くの再帰的な呼び出し（ベースケースを正確に提供しないか、またはあまりにも多くの再帰呼び出しを試みることによる）を行うと、すべてのためのスペースを確保する余地がなくなり、StackOverflow 。

ループにこの問題がないのは、ループの各反復で独自のスペースが使用されないためです（つまり、n回ループすると、n+1ループを実行するために余分なスペースは必要ありません）。

Answer 7

再帰がスタックオーバーフローを引き起こす理由は、再帰がいつ停止するべきかを確かめることができないためです。したがって、関数/メソッドは自分自身を "永遠に"（エラーを引き起こすまで）呼び出し続けます。 flagは常にtrueになりますので、それはあなたのスタックオーバーフローエラーを与えるまで、whileループを停止することはありません

bool flag = true; 
while (flag == true){ 
    count++; 
} 

：あなたは、ループを使用している場合でも、あなたは、次のようなものを持っている場合は、同じ問題を抱えているだろう。

Answer 8

すべてのレベルの再帰が実行されると、ランタイムスタックに状態情報が追加されます。この情報はアクティベーションレコードに格納され、どの変数が有効で、その値がどのようなものかなどの情報が含まれています。ループするたびに余分なアクティベーションレコードがありません。

特定の状況では、再帰が深くなりすぎてスタックがオーバーフローすることがありますが、これが起こらないようにする方法があります。再帰で作業する場合、私は通常、この形式は、次のとおりです。

public obj MyMethod(string params) { 
    if (base-case) { 
     do something... 
    } else { 
     do something else... 
     obj result = MyMethod(parameters here); 
     do something else if needed.. 
    } 
} 

再帰は超効果的であるとすることはできませんループのことを行うことができます。場合によっては、再帰が明らかな決定である点にたどり着くこともあります。あなたが良いプログラマーになるのは、それが完全にobvoiusでないときにそれを使用できることです。