由于递归导致的java.lang.StackOverflowError [英] java.lang.StackOverflowError due to recursion
问题描述
我的问题是，当我使用递归时，我通常会得到一个java.lang.StackOverflowError。
我的问题是 - 为什么递归导致stackoverflow比循环更多，有没有什么好的方法使用递归来避免堆栈溢出？
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;
}
}
推荐答案
为什么递归导致stackoverflow比循环更多
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屋！
