Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Recursive method - stack overflow

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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;

    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);                   
    }
    }


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Recursive method - stack overflow

    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.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Apr 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Recursive method - stack overflow

    Quote Originally Posted by Norm View Post
    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.

    Thank you for replying

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Apr 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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 View Post
    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:

    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);                   
    }
    }

Similar Threads

  1. help with recursive method
    By mflb94 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2012, 06:30 PM
  2. [SOLVED] Banker Deadlock detection algorith going haywire and likely a stack overflow error
    By javapenguin in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 23rd, 2012, 05:23 PM
  3. [SOLVED] stack overflow error
    By Goldfinch in forum What's Wrong With My Code?
    Replies: 14
    Last Post: February 3rd, 2012, 01:07 AM
  4. Replies: 3
    Last Post: January 6th, 2012, 09:18 AM
  5. Replies: 0
    Last Post: October 14th, 2008, 06:40 PM