Java.lang.StackOverflowError due to recursion

Question

My problem is that I usually get java.lang.StackOverflowError when I use recursion. My question is: why does recursion call stackoverflow much more than loops, and is there a good way to use recursion to avoid?

This is an attempt to solve problem 107, it works well for their example, but ends out of the stack space for the problem. / p>

//-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 recursion causes stackoverflow so much more than loops

Because each recursive call uses some space on the stack. If your recursion is too deep, then this will lead to StackOverflow , depending on the maximum allowed depth on the stack.

When using recursion, you have to be very careful and make sure that you provide the base unit. The base register in recursion is the condition on the basis of which recursion ends and the stack begins to spin. This is the main reason for recursion causing a StackOverflow error. If it does not find the base register, it will go into infinite recursion, which will undoubtedly lead to an error, since the Stack is finite.

Answer 2

In most cases, the stack overflow occurs because the recursive method has not been defined, with a nonexistent or unattainable final condition, due to which the memory space of the stack will be exhausted. A correctly written recursion should not lead to a stack overflow.

However, there are situations where a method can create a stack overflow, even if it was correctly implemented. For example:

• Fast-growing (say, exponential) recursion. For example: a naive recursive implementation of the Fibonacci function
• Very large input, which ultimately leads to the exhaustion of the stack space.

Bottom line: it all depends on the specific case, it is impossible to generalize what causes the stack to overflow.

Answer 3

Each recursive call uses some space on the stack (to place something specific for that call, such as arguments, local variables, etc.). Thus, if you make too many recursive calls (either by incorrectly providing the base code, or simply trying to make too many recursive calls), then there is not enough space to provide space for all of this, and you will get StackOverflow .

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

Answer 4

When used correctly, recursion does not StackOverflowError . If so, then your base register does not start, and the method continues to call itself infinite. Each method call that does not complete remains on the stack, and eventually it overflows.

But loops themselves do not include method calls, so nothing happens on the stack, and a StackOverflowError fails.

Answer 5

Each time you call a method, you consume a "frame" from the stack, this frame is not output until the method returns, it will not coincide with the cycles.

Answer 6

Recursion

causes a stack overflow because all previous calls are in memory. therefore, your method calls itself with new parameters, and then calls itself again. therefore, all these calls add up and can usually end in memory. loops usually store results in some variables and call methods that look like a new fresh method call; after each call, the caller’s methods end and return the results.

Answer 7

The reason that recursion causes the stack to overflow is because we cannot determine when the recursion should stop, and therefore the function / method will continue to call itself “forever” (until it causes an error). You will have the same problem, even if you use loops, if you have something in the following:

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

Since flag will always be true, the while loop will never stop until it gives you an error.

Answer 8

Each recursion level that you omit adds state information to the execution stack. This information is stored in the activation record and contains information about which variables are in scope and what are their values. Loops do not have additional activation records each time you loop so that they take up less memory.

In certain situations, your recursion may be deep enough to cause a stack overflow, but there are ways to prevent this. 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 efficient and do what loops cannot. Sometimes you just get to the point where recursion is the obvious solution. What makes you a good programmer can use it when it is not completely obvoius.