12

私の問題は、再帰を使用すると通常 java.lang.StackOverflowError が発生することです。私の質問は、再帰がループよりも多くのスタックオーバーフローを引き起こすのはなぜですか?再帰を使用してスタックオーバーフローを回避する良い方法はありますか?

これは問題 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;
    }
}
4

10 に答える 10

21

なぜ再帰はループよりも多くのスタックオーバーフローを引き起こすのですか

各再帰呼び出しはスタック上のスペースを使用するためです。再帰が深すぎる場合StackOverflow、スタックで許可される最大深さに応じて、結果は になります。

再帰を使用する場合は、細心の注意を払い、base caseを提供するようにしてください。再帰の基本ケースは、再帰が終了し、スタックが巻き戻しを開始する条件です。StackOverflowこれが、再帰がエラーを引き起こす主な理由です。基本ケースが見つからない場合、無限再帰に入り、Stack有限のみの場合と同様に、間違いなくエラーになります。

于 2013-08-21T21:59:18.083 に答える
6

ほとんどの場合、スタック オーバーフローは、再帰メソッドが不適切に定義されていて、終了条件が存在しないか到達不能であり、スタック メモリ領域が使い果たされるために発生します。再帰が正しく記述されていれば、スタック オーバーフローは発生しません。

ただし、メソッドが正しく実装されていても、メソッドによってスタック オーバーフローが発生する場合があります。例えば：

  • 急速に成長する (たとえば、指数関数的な) 再帰。例: フィボナッチ関数の単純な再帰的実装
  • 非常に大きな入力データ。最終的にスタック スペースが使い果たされます。

結論: それはすべて特定のケースに依存します。スタック オーバーフローの原因について一般化することは不可能です。

于 2013-08-21T21:59:41.720 に答える
3

各再帰呼び出しは、スタック上のスペースを使用します (引数、ローカル変数など、その 1 つの呼び出しに固有のものを格納するため)。したがって、再帰呼び出しが多すぎると (基本ケースを正しく提供しないか、単に再帰呼び出しを何度も実行しようとするかのいずれかによって)、それらすべてにスペースを提供する十分なスペースがなく、StackOverflow.

ループにこの問題がない理由は、ループの各反復が独自の一意のスペースを使用しないためです (つまり、ループ時間を繰り返す場合、 st ループnを実行するために余分なスペースは必要ありません)。n+1

于 2013-08-21T22:03:12.213 に答える
1

再帰のレベルを下げるたびに、状態情報がランタイム スタックに追加されます。この情報はアクティベーション レコードに保存され、スコープ内の変数やその値などの情報が含まれます。ループには、ループするたびに追加のアクティベーション レコードがないため、使用するメモリが少なくなります。

特定の状況では、再帰が深すぎてスタックがオーバーフローすることがありますが、これを防ぐ方法があります。再帰を扱うときは、通常、次の形式に従います。

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

再帰は非常に効果的で、ループではできないことを行うことができます。場合によっては、再帰が当然の決定になるポイントにたどり着くことがあります。あなたを優れたプログラマーにするのは、それが完全にわかりにくいときにそれを使用できることです。

于 2013-08-21T22:10:59.570 に答える
0

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

ただし、ループ自体にはメソッド呼び出しは含まれないため、スタックには何も蓄積されず、aStackOverflowErrorは発生しません。

于 2013-08-21T21:59:28.293 に答える
0

メソッドを呼び出すたびに、スタックから「フレーム」を消費します。このフレームは、メソッドが戻るまで解放されません。ループでは同じことは起こりません。

于 2013-08-21T21:59:34.947 に答える
0

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

于 2013-08-21T22:01:32.880 に答える
0

再帰によってスタック オーバーフローが発生する理由は、再帰を停止するタイミングを確立できず、関数/メソッドが (エラーが発生するまで) 自身を「永久に」呼び出し続けるためです。次のようなものがある場合、ループを使用していても同じ問題が発生します。

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

は常に true になるためflag、スタック オーバーフロー エラーが発生するまで while ループは停止しません。

于 2013-08-21T22:06:38.370 に答える