Recursive method - stack overflow

• April 8th, 2013, 05:05 AM
yakir_g
Recursive method - stack overflow
Hello, I'm writing a recursive method to find all the possible paths in a two dimensional array. From the top left point (0,0) to the bottom right point last point. And returns the sums of the paths.
This method does the first step right and prints the sum of the first path and then suppose to traverse, so back to the last element and check if it could go in another direction, back one more and do the same.
If it's possible it goes to the new direction and continues to the end from there.
If not it returns one more step again.
This precess repeats until the last element to check is the first one and then when there's no more elements to check, exit.

Don't mind the sum problem for now, I just get a stack overflow..
Thank you :)

Here's my code;

Code :

```public class AllPos{   public static boolean valid(int[][] m,int row,int col){ if(row>=0 && row <m.length && col>=0 && col <m[row].length) return true; else return false; }   public static void printPathWeights(int[][] m){ printPathWeights(m,0,0,0);//m,row,col.sum }   public static void printPathWeights(int[][] m,int row,int col,int sum){   if(row == 0 && col ==0) sum = 0;   if(m.length-1 == row && m[row].length-1 == col){ System.out.println(sum); return; }   else{ if(valid(m,row+1,col)) printPathWeights(m,row+1,col,sum+=m[row][col]); //down if(valid(m,row,col+1)) printPathWeights(m,row,col+1,sum+=m[row][col]); //right if((valid(m,row-1,col)) && (row < m.length-1)) printPathWeights(m,row,col-1,sum+=m[row][col]); //left }   return; }   public static void main (String args[]){ int [][] matrix = {{8,4,2,4,3}, {6,3,8,4,5}, {1,4,9,9,7}, {2,1,7,6,5}};   printPathWeights(matrix); } }```
• April 8th, 2013, 06:06 AM
Norm
Re: Recursive method - stack overflow
Quote:

I just get a stack overflow..
Can you post some of the error message that shows where the methods are being called recursively? What variables should stop the recursive calls? What are their values as the calls are being made? Add some println statements to show their values so you can see what the problem is.
• April 8th, 2013, 06:39 AM
yakir_g
Re: Recursive method - stack overflow
Quote:

Originally Posted by Norm
Can you post some of the error message that shows where the methods are being called recursively? What variables should stop the recursive calls? What are their values as the calls are being made? Add some println statements to show their values so you can see what the problem is.

I'm getting allot of prints and then the error: java.lang.StackOverflowError
at sun.nio.cs.UTF_8\$Encoder.encodeLoop(UTF_8.java:466 )

since it's a void I thought when all the recursive calls are over, the method will just exit. I don't need it to return anything since I use System.out.println to print all the paths sums.

• April 8th, 2013, 06:46 AM
Norm
Re: Recursive method - stack overflow
Are you saying that the loop is NOT in your code?
Where is the looping method called from your code?
• April 8th, 2013, 07:38 AM
yakir_g
Re: Recursive method - stack overflow
I think it was because my memory ran out :) My computer is really short of ram lately gonna add some ram soon. I have reduced the array size and had no problem with the stack.
All I have to do now is working on the sum that should reset itself when reached to the end. Hopefully will go well.

Thanks again Norm, glad to join the forum.

--- Update ---

Quote:

Originally Posted by Norm
Are you saying that the loop is NOT in your code?
Where is the looping method called from your code?

Basically I didn't want to use any kind of loop beside recursive calls.
In this example it's a collection of backward and forward actions, a bit complicated for me to explain.
The best way to explain it is to run a debugger on it.

Here's my solution with a smaller matrix:

Code :

```public class AllPos{   public static boolean valid(int[][] m,int row,int col){ if(row>=0 && row <m.length && col>=0 && col <m[row].length) return true; else return false; }   public static void printPathSums(int[][] m){ printPathSums(m,0,0,0);//m,row,col.sum }   public static void printPathSums(int[][] m,int row,int col,int sum){   if(row == 0 && col ==0) sum = 0;   if((m.length-1 == row && m[row].length-2 == col) || (m.length-2 == row && m[row].length-1 == col)){ if(m.length-1 == row && m[row].length-2 == col) sum+=m[m.length-1][m[0].length-2]; else sum+=m[m.length-2][m[0].length-1];   sum+=m[m.length-1][m[0].length-1]; System.out.println(sum); printPathSums(m,m.length-1,m[0].length-1,0); }   if(m.length-1 == row && m[row].length-1 == col){ return; }   else{ if(valid(m,row+1,col)) printPathSums(m,row+1,col,sum+=m[row][col]); //down if(valid(m,row,col+1)) printPathSums(m,row,col+1,sum+=m[row][col]); //right if((valid(m,row-1,col)) && (row < m.length-1)) printPathSums(m,row,col-1,sum+=m[row][col]); //left }   return; }   public static void main (String args[]){   int [][] matrix2={{8,4,2,4,3}, {2,1,7,6,5}};   printPathSums(matrix2); } }```