我的问题是,当我使用递归时,我通常会得到一个java.lang.StackOverflowError。我的问题是 - 为什么递归导致stackoverflow比循环更多,并且是否有任何使用递归来避免堆栈溢出的好方法?
这是一个尝试解决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&©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比循环更多
因为每个递归调用都使用堆栈上的一些空间。如果递归太深,那么它将导致StackOverflow
,具体取决于堆栈中允许的最大深度。
使用递归时,您应该非常小心并确保提供base case。递归中的基本情况是递归结束的条件,堆栈开始展开。这是导致StackOverflow
错误的递归的主要原因。如果它没有找到任何基本情况,它将进入无限递归,这肯定会导致错误,因为Stack
只是有限的。
在大多数情况下,发生堆栈溢出是因为递归方法定义不明确,并且存在不存在或不可达的结束条件,这会导致堆栈内存空间耗尽。正确写入的递归不应产生堆栈溢出。
但是,有些情况下,即使正确实现了方法,方法也会产生堆栈溢出。例如:
底线:这一切都取决于具体情况,因此不可能对导致堆栈溢出的原因进行概括。
每个递归调用都使用堆栈上的一些空间(用于容纳特定于该一个调用的任何内容,例如参数,局部变量等)。因此,如果您进行了太多的递归调用(通过不正确地提供基本情况或仅仅通过尝试执行太多的递归调用),那么就没有足够的空间来为它提供所有空间,并且最终得到了StackOverflow
。
循环没有这个问题的原因是循环的每次迭代都不使用它自己的唯一空间(即如果我循环n
次,我不需要额外的空间来执行n+1
st循环)。
每次调用一个方法时,都会从堆栈中使用一个“框架”,这个框架在方法返回之前不会释放,它与循环不会发生相同的情况。
您下载的每个级别的递归,都是将状态信息添加到运行时堆栈。此信息存储在激活记录中,并包含诸如变量在范围内以及它们的值是什么的信息。每次循环时循环都没有额外的激活记录,因此它们占用的内存较少。
在某些情况下,您的递归可能会变得足够深,导致堆栈溢出,但有一些方法可以帮助防止这种情况发生。使用递归时,我通常遵循以下格式:
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。
正确使用时,递归不会产生StackOverflowError
。如果确实如此,那么你的基本情况就不会被触发,并且该方法一直无限地调用自己。每个未完成的方法调用都会保留在堆栈中,最终会溢出。
但循环本身不涉及方法调用,因此堆栈上没有任何东西,并且不会产生StackOverflowError
。
递归导致堆栈溢出导致所有先前的调用都在内存中。所以你的方法用新参数调用自己,然后再调用自己。因此所有这些调用都会堆叠起来并且通常会耗尽内存。循环通常将结果存储在某些变量中并调用方法,这类似于对方法的全新调用,每次调用后,调用方法结束并返回结果。
递归导致堆栈溢出的原因是因为我们无法确定何时应该停止递归,因此函数/方法将继续“永久”调用自身(直到它导致错误)。即使您使用循环,如果您有以下内容,您将遇到同样的问题:
bool flag = true;
while (flag == true){
count++;
}
由于flag
将始终为true,因此while循环将永远不会停止,直到它为您提供堆栈溢出错误。