我的问题是，当我使用递归时，通常会得到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&©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，这取决于堆栈中允许的最大深度。
当使用递归时，您应该非常小心，并确保您提供了一个基本情况。递归的基本情况是递归结束和堆栈开始展开的条件。这是递归导致StackOverflow错误的主要原因。如果它找不到任何基本情况，它将进入无限递归，这肯定会导致错误，因为Stack只是有限的。
在大多数情况下，堆栈溢出是因为递归方法定义不正确，具有不存在或无法访问的结束条件，这会导致堆栈内存空间耗尽。正确编写的递归不应产生堆栈溢出。
但是，在某些情况下，如果方法实现正确，它可能会产生堆栈溢出，甚至。例如：
- 一种快速增长的（比如指数）递归。例如：斐波那契函数的朴素递归实现
- 一个非常大的输入数据，最终会导致堆栈空间耗尽
一句话：这完全取决于特定的情况，不可能概括导致堆栈溢出的原因。
每个递归调用都会在堆栈上使用一些空间（用来容纳特定于该调用的任何东西，如参数、局部变量等）。因此，如果你进行了太多的递归调用（要么是因为没有正确地提供基本情况，要么只是因为试图进行太多递归调用），那么就没有足够的空间为所有调用提供空间，最后你得到了StackOverflow。
循环没有这个问题的原因是循环的每次迭代都不使用自己的唯一空间（即，如果我循环n次，我就不需要额外的空间来执行n+1次循环）。
递归导致堆栈溢出的原因是我们无法确定递归何时停止，因此函数/方法将"永远"调用自己（直到它导致错误）。即使你使用循环，如果你有以下内容，你也会遇到同样的问题：
bool flag = true;
while (flag == true){
count++;
}
由于flag将始终为true，while循环将永远不会停止，直到它给您提供堆栈溢出错误。
每降低一级递归，都会将状态信息添加到运行时堆栈中。这些信息存储在激活记录中，并包含诸如哪些变量在作用域中以及它们的值等信息。每次循环时，循环没有额外的激活记录，因此占用的内存较少。
在某些情况下，递归可能会深入到导致堆栈溢出的程度，但有一些方法可以帮助防止这种情况发生。当使用递归时，我通常遵循以下格式：
public obj MyMethod(string params) {
if (base-case) {
do something...
} else {
do something else...
obj result = MyMethod(parameters here);
do something else if needed..
}
}
递归可以非常有效，并且可以做循环不能做的事情。有时，递归是显而易见的决定。让你成为一名优秀程序员的原因是能够在不完全显而易见的情况下使用它。
如果使用得当，递归将不会产生StackOverflowError。如果是这样，那么你的基本情况就不会被触发，方法会无限地调用自己。每个未完成的方法调用都保留在堆栈上，最终会溢出。
但是循环本身并不涉及方法调用，因此堆栈上不会生成任何内容，也不会生成StackOverflowError。
每次调用一个方法时，都会从堆栈中消耗一个"帧"，直到方法返回，这个帧才会释放，循环的情况就不一样了。
递归会导致堆栈溢出，因为之前的所有调用都在内存中。因此，您的方法使用新参数调用自己，然后再次调用自己。所以所有这些调用都会堆积起来，并且通常会耗尽内存。循环通常将结果存储在一些变量中，并调用方法，这就像对方法的新的新调用一样，每次调用后，调用方方法结束并返回结果。
在我看来，由于以下原因，递归中出现StackOverFlow错误：
-
没有正确实现递归，导致无限递归，所以请检查基本情况等。
-
如果您的输入很大，则最好使用Tail Recursion来避免StackOverflow。
此处for loop用于recursive function内部。当递归函数被调用时，for(int i=0; i<n; i++)，i的值被初始化为零，当它调用自己时，i的数值将再次被初始化为0，并且它无穷大。这将导致堆栈溢出错误。
解决方案：避免在递归函数中使用for loop；而是转到while or do-while，并在递归函数外部初始化i的值