java.lang.StackOverflowError due to recursion
java, recursion, stack-overflow
Solution
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.
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 `StackOverflow` error. If it doesn't find any base case, it will go into an infinite recursion, which will certainly result in error, as `Stack` is finite only.
Problem
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? 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. ``` //-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&©OfMatrix[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; } } ```