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

Question

我的问题是,当我使用递归时,我通常会得到一个java.lang.StackOverflowError.我的问题是 - 为什么递归导致stackoverflow比循环更多,并且是否有任何使用递归来避免堆栈溢出的好方法？

这是一个解决问题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

为什么递归导致stackoverflow比循环更多

因为每个递归调用都使用堆栈上的一些空间.如果您的递归太深,那么它将导致StackOverflow,具体取决于堆栈中允许的最大深度.

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

Answer 2

大多数情况下，堆栈溢出的发生是因为递归方法定义不明确，结束条件不存在或不可达，导致堆栈内存空间耗尽。正确编写的递归不应产生堆栈溢出。

但是，在某些情况下，即使正确实现了方法，也可能会产生堆栈溢出。例如：

• 快速增长（例如，指数）递归。例如：斐波那契函数的朴素递归实现
• 非常大的输入数据，最终会导致栈空间耗尽

底线：这完全取决于特定情况，无法概括导致堆栈溢出的原因。