由于递归导致的 java.lang.StackOverflowError

Question

我的问题是，当我使用递归时，我通常会遇到 java.lang.StackOverflowError 。 我的问题是 - 为什么递归比循环更容易导致堆栈溢出，有没有什么好的方法可以使用递归来避免堆栈溢出？

这是尝试解决 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&&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;
    }
}

Answer 1

why does recursion cause stackoverflow so much more than loops do

因为每次递归调用都会占用堆栈上的一些空间。如果递归太深，则会导致 StackOverflow，具体取决于堆栈中允许的最大深度。

使用递归时，您应该非常小心并确保提供 base case 。递归中的基本情况是递归结束且堆栈开始展开的条件。这是递归导致 StackOverflow 错误的主要原因。如果没有找到任何基本情况，它将进入无限递归，这肯定会导致错误，因为 Stack 只是有限的。