由于递归导致的 java.lang.StackOverflowError [英] java.lang.StackOverflowError due to recursion
问题描述
我的问题是，当我使用递归时，我通常会得到一个 java.lang.StackOverflowError.我的问题是 - 为什么递归比循环更能导致堆栈溢出，是否有任何使用递归来避免堆栈溢出的好方法?
My problem is that I usually get a java.lang.StackOverflowError when I use recursion. My question is - why does recursion cause stackoverflow so much more than loops do, and is there any good way of using recursion to avoid stack overflow?
这是解决问题107的尝试，对于他们的示例来说效果很好，但堆栈用完了问题本身的空间.
This is an attempt to solve problem 107, it works well for their example but runs out of stack space for the problem it self.
//-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&©OfMatrix[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;
}
}
推荐答案
为什么递归比循环更能引起计算器溢出
why does recursion cause stackoverflow so much more than loops do
因为每次递归调用都会占用堆栈上的一些空间.如果您的递归太深，则会导致 StackOverflow，具体取决于堆栈中允许的最大深度.
Because each recursive call uses some space on the stack. If your recursion is too deep, then it will result in StackOverflow, depending upon the maximum allowed depth in the stack.
在使用递归时，您应该非常小心并确保提供基本情况.递归中的基本情况是递归结束和堆栈开始展开的条件.这是递归导致 StackOverflow 错误的主要原因.如果它没有找到任何基本情况，它将进入无限递归，这肯定会导致错误，因为Stack只是有限的.
When using recursion, you should be very careful and make sure that you provide a base case. A base case in recursion is the condition based on which the recursion ends, and the stack starts to unwind. This is the major reason of recursion causing StackOverflow error. If it doesn't find any base case, it will go into an infinite recursion, which will certainly result in error, as Stack is finite only.
这篇关于由于递归导致的 java.lang.StackOverflowError的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
