12

我的问题是，当我使用递归时，我通常会得到一个 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&&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;
    }
}
4

10 回答 10

21

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

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

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

于 2013-08-21T21:59:18.083 回答
6

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

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

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

底线：这完全取决于特定情况，不可能一概而论导致堆栈溢出的原因。

于 2013-08-21T21:59:41.720 回答
3

每个递归调用都使用堆栈上的一些空间（以容纳特定于该调用的任何内容，例如参数、局部变量等）。因此，如果你进行了太多递归调用（要么没有正确提供基本情况，要么只是尝试进行太多递归调用），那么就没有足够的空间来为所有这些提供空间，你最终会得到一个StackOverflow.

循环没有这个问题的原因是循环的每次迭代都没有使用它自己独特的空间（即如果我循环n次数，我不需要额外的空间来做n+1st循环）。

于 2013-08-21T22:03:12.213 回答
1

您向下的每一级递归，您都将状态信息添加到运行时堆栈。此信息存储在激活记录中，并包含诸如哪些变量在范围内以及它们的值是什么等信息。每次循环时，循环都没有额外的激活记录，因此它们占用的内存更少。

在某些情况下，您的递归可能会深入到导致堆栈溢出，但有一些方法可以帮助防止这种情况发生。使用递归时，我通常遵循以下格式：

public obj MyMethod(string params) {
    if (base-case) {
        do something...
    } else {
        do something else...
        obj result = MyMethod(parameters here);
        do something else if needed..
    }
}

递归可以非常有效，并且可以做循环不能做的事情。有时你只是到了递归是显而易见的决定的地步。使您成为一名优秀程序员的原因是能够在它不完全明显的情况下使用它。

于 2013-08-21T22:10:59.570 回答
0

递归导致堆栈溢出，因为所有先前的调用都在内存中。所以你的方法用新参数调用自己，然后再次调用自己。所以所有这些调用都会堆积起来，通常会耗尽内存。循环通常将结果存储在一些变量中并调用方法，这就像对方法的新调用一样，每次调用后，调用者方法结束并返回结果。

于 2013-08-21T22:01:32.880 回答
0

如果使用得当，递归不会产生StackOverflowError. 如果是这样，那么您的基本情况不会被触发，并且该方法会无限地调用自己。每个未完成的方法调用都保留在堆栈上，并最终溢出。

但是循环本身不涉及方法调用，因此堆栈上不会建立任何内容，并且StackOverflowError不会产生 a 。

于 2013-08-21T21:59:28.293 回答
0

每次调用方法时，都会从堆栈中消耗一个“帧”，在方法返回之前不会释放该帧，循环不会发生相同的情况。

于 2013-08-21T21:59:34.947 回答
0

递归导致堆栈溢出的原因是因为我们无法确定递归应该何时停止，因此函数/方法将“永远”保持调用自身（直到它导致错误）。即使您使用循环，您也会遇到同样的问题，如果您有以下内容：

bool flag = true;
while (flag == true){
   count++;
}

由于flag将始终为真，while 循环将永远不会停止，直到它给你堆栈溢出错误。

于 2013-08-21T22:06:38.370 回答
0

在我看来，由于以下原因，在递归中出现 StackOverFlow 错误：

  1. 未正确实现递归，导致无限递归，因此请检查基本情况等。

  2. 如果您的输入很大，最好使用尾递归来避免 StackOverflow。

于 2020-08-20T14:54:29.530 回答
-1

这里for loop用在recursive function. 当递归函数被调用时，for(int i=0; i<n; i++)i 的值被初始化为零，当它调用自身时，i 的值将再次被初始化为零并且它无限地继续。这将导致您出现堆栈溢出错误。

解决方案：避免for loop内部递归函数；而是while or do-while在递归函数之外寻找并初始化 i 的值

于 2020-01-22T07:08:38.523 回答