java.lang.StackOverflowError 由于递归

java.lang.StackOverflowError due to recursion

提问by user2705335

My problem is that I usually get a java.lang.StackOverflowError when I use recursion. My question is - why does recursion cause stackoverflow so much more than loops do, and is there any good way of using recursion to avoid stack overflow?

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

This is an attempt to solve problem 107, it works well for their example but runs out of stack space for the problem it self.

这是解决问题 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;
    }
}

回答by Rohit Jain

why does recursion cause stackoverflow so much more than loops do

为什么递归比循环更能引起计算器溢出

Because each recursive call uses some space on the stack. If your recursion is too deep, then it will result in StackOverflow, depending upon the maximum allowed depth in the stack.

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

When using recursion, you should be very careful and make sure that you provide a base case. A base case in recursion is the condition based on which the recursion ends, and the stack starts to unwind. This is the major reason of recursion causing StackOverflowerror. If it doesn't find any base case, it will go into an infinite recursion, which will certainly result in error, as Stackis finite only.

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

回答by rgettman

When properly used, recursion will not produce a StackOverflowError. If it does, then your base case is not being triggered, and the method keeps calling itself ad infinitum. Every method call that does not complete remains on the stack, and eventually it overflows.

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

But loops don't involve method calls by themselves, so nothing builds up on the stack and a StackOverflowErrordoes not result.

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

回答by morgano

Every time you call a method, you consume a "frame" from the stack, this frame is not released until the method returns, it doesn't happen the same with loops.

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

回答by óscar López

In most cases, a stack overflow occurs because a recursive method was ill-defined, with a non-existent or unreachable ending condition, which causes the stack memory space to be exhausted. A correctly written recursion should not produce a stack overflow.

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

However, there are situations where a method can produce a stack overflow evenif it was correctly implemented. For instance:

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

• A fast-growing (say, exponential) recursion. For example: the naive recursive implementation of the Fibonacci function
• A very big input data, that will eventually cause the stack space to be exhausted

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

Bottom line: it all depends on the particular case, it's impossible to generalize regarding what causes a stack overflow.

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

回答by Ashish Thukral

recursion causes stack overflow cause all the previous calls are in memory. so your method calls itself with new parameters, then that again calls itself. so all these calls stack up and normally can run out of memory. loops store the results normally in some variables and call the methods which is like a new fresh call to methods, after each call, the caller methods ends and returns results.

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

回答by Dennis Meng

Each recursive call uses some space on the stack (to house anything specific to that one call, such as arguments, local variables, etc.). Thus, if you make too many recursive calls (either by not correctly providing a base case or just by trying to do too many recursive calls), then there is not enough room to provide space for it all, and you end up with a StackOverflow.

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

The reason why loops do not have this problem is that each iteration of a loop does not use its own unique space (i.e. if I loop ntimes, I don't need extra space to do the n+1st loop).

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

回答by Anna

The reason why the recursion causes stack overflow is because we fail to establish when the recursion should stop, and thus the function/method will keep calling itself "forever" (until it causes the error). You will have the same problem even if you are using loops, if you have something as the following:

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

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

Since flagwill always be true, the while loop will never stop until it gives you the stack overflow error.

因为flag永远是真的，while 循环永远不会停止，直到它给你堆栈溢出错误。

回答by TJS

Every level of recursion that you go down, you are add state information to the runtime stack. This information is stored in an activation record and contains information like which variables are in scope and what their values are. Loops do not have extra activation records each time you loop so they take less memory.

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

In certain situations your recursion may go deep enough that it causes the stack to overflow but there are ways to help prevent this from happening. When working with recursion, I usually follow this format:

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

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

Recursion can be super effective and do things that loops cannot. Sometimes you just get to a point where recursion is the obvious decision. What makes you a good programmer is being able to use it when it is not completely obvoius.

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

回答by marla

Here for loopis used inside the recursive function. When the recursive function is called, for(int i=0; i<n; i++)the value of i is initialized to zero, as it calls itself, the value of i will again be initialized to zero and it conitues infintely. This will lead you to Stack overflow error.

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

Solution: Avoid for loopinside recursive function; instead go for while or do-whileand initialize the value of i outside recursive function

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