Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By ozzyman

Thread: Recursion error

  1. #1
    jcarosella10 is offline Member
    Join Date
    Mar 2012
    Location
    Vestal, NY
    Posts
    36
    Rep Power
    0

    Default Recursion error

    I'm writing a simple recursion program that is supposed to find a path through a "maze".
    Java Code:
    //CLASS MAZESEARCH (driver)
    public class MazeSearch
    {
        public static void main(String[] args)
        {
            Maze labyrinth = new Maze();
            System.out.println(labyrinth);
            if(labyrinth.traverse(0, 0))
            {
                System.out.println("The maze was successfully solved!");
            }
            else
            {
                System.out.println("There is no possible path.");
            }
            System.out.println(labyrinth);
        }
    }
    //CLASS MAZE
    public class Maze
    {
        private final int TRIED = 3;
        private final int PATH = 7;
        private int[][] grid = {    {1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1},
                                    {1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},
                                    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
                                    {1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
                                    {1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
                                    {1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
                                    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                                    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
        public boolean traverse(int row, int column)
        {
            boolean done = false;
            if(valid(row, column))
            {
                grid[row][column] = TRIED;
                if(row == grid.length - 1 && column == grid[0].length - 1)
                {
                    done = true;
                }
                else
                {
                    done = traverse(row + 1, column + 1);
                    if(!done)
                    {
                        done = traverse(row, column + 1);
                    }
                    if(!done)
                    {
                        done = traverse(row - 1, column);
                    }
                    if(!done)
                    {
                        done = traverse(row, column - 1);
                    }
                }
                if(done)
                {
                    grid[row][column] = PATH;
                }
            }
            return done;
        }
        private boolean valid(int row, int column)
        {
            boolean result = false;
            if(row >= 0 && row < grid.length && column >= 0 && column < grid[row].length)
            {
                if(grid[row][column] == 1)
                {
                    result = true;
                }
            }
            return result;
        }
        public String toString()
        {
            String result = "\n";
            for(int row = 0; row < grid.length; row++)
            {
                for(int column = 0; column < grid[row].length; column++)
                {
                    result += grid[row][column] + "";
                }
                result += "\n";
            }
            return result;
        }
    }
    Here is the output:
    "1110110001111
    1011101111001
    0000101010100
    1110111010111
    1010000111001
    1011111101111
    1000000000000
    1111111111111

    There is no possible path.

    3330330003333
    1033303333003
    0000303030300
    1110333030333
    1010000333003
    1011111103333
    1000000000000
    1111111111111"

    Theres the problem in red...why is it not seeing that 1 below the 3 on the left?

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,418
    Rep Power
    25

    Default Re: Recursion error

    why is it not seeing that 1 below the 3 on the left?
    Add some printlns to the code to print out what it is doing so you can see where the execution goes and what the values of variables are as it executes

  3. #3
    ozzyman's Avatar
    ozzyman is offline Senior Member
    Join Date
    Mar 2011
    Location
    London, UK
    Posts
    797
    Blog Entries
    2
    Rep Power
    4

    Default Re: Recursion error

    I'm not really sure I understand your code but it just seems like this part:
    Java Code:
                    done = traverse(row + 1, column + 1);
                    if(!done)                {
                        done = traverse(row, column + 1);
                    }
                    if(!done)                {
                        done = traverse(row - 1, column);
                    }
                    if(!done)                {
                        done = traverse(row, column - 1);
                    }
    is meant to search up,down,left and right from a given index in the 2d array...

    if thats so, then the first statement is wrong and should look like this:
    Java Code:
                    done = traverse(row + 1, column);
    so that you are checking 'down' and not 'down-right'


    looking at your output again it seems like all of the 1's that were converted to 3's were accessible through the down-right path up until where it had stopped.
    Last edited by ozzyman; 03-11-2012 at 01:57 AM.
    jcarosella10 likes this.

  4. #4
    jcarosella10 is offline Member
    Join Date
    Mar 2012
    Location
    Vestal, NY
    Posts
    36
    Rep Power
    0

Similar Threads

  1. recursion help
    By Yakg in forum New To Java
    Replies: 6
    Last Post: 02-18-2011, 01:10 PM
  2. Replies: 1
    Last Post: 03-17-2010, 05:25 AM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  4. Recursion with int and string error message
    By nicolek808 in forum New To Java
    Replies: 7
    Last Post: 09-14-2009, 09:30 AM
  5. recursion
    By ravian in forum New To Java
    Replies: 2
    Last Post: 12-03-2007, 05:15 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •