Results 1 to 5 of 5
  1. #1
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    5

    Default Recursive method infinitely looping

    I wrote this method to solve Problem 15 of Project Euler:

    Java Code:
    public class Problem15 {
    	static int RecursivePathFind(int i, int j) {
    		int result = 0;
    		if(i < 20) {
    			result += 1 + RecursivePathFind(i+1, j);
    		}
    		if(j < 20) {
    			result += 1 + RecursivePathFind(i, j+1);
    		}
    		return result;
    	}
    	public static void main(String[] args) {
    		System.out.println(RecursivePathFind(0,0)/40); // Each path is 40 steps
    	}
    }
    Any idea why it's not terminating?

    EDIT - Disregard the above; apparently the method works, but it takes a very long time to do so and also exceeds the bounds of an int.

    Is there a more efficient way of doing this?
    Last edited by Iron Lion; 01-22-2011 at 06:30 PM.

  2. #2
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    You'll need to use BigInteger to get around the limits of int, and you can improve the efficiency by implementing memoization.

    Your method is not really a proper recursive method, and you've got "magic numbers" in several places. You want a method where you can call recursivePathFind(2, 2) and get the result 6 as the example shows. As in every recursive method, you need to identify your base cases and check for them. Then if you find that your current situation is not a base case, you take a simple step that involves solving a simpler version of the problem you're trying to solve.

    In this case, you are starting at the upper left corner of a grid, and trying to move to the bottom right corner. Let's call the bottom right corner (0, 0) -- if we're already there, then we're all done, and our method can return 0.

    Java Code:
    [COLOR="Blue"]        public BigInteger pathCount(int x, int y) {
                    if (x == 0 && y == 0) return BigInteger.ZERO;
            }
    [/COLOR]
    If we're at the bottom edge or at the right edge, then there's only one path remaining to get to the bottom right.

    Java Code:
            public BigInteger pathCount(int x, int y) {
                    if (x == 0 && y == 0) return BigInteger.ZERO;
    [COLOR="Blue"]                if (x == 0) return BigInteger.ONE;
                    if (y == 0) return BigInteger.ONE;
    [/COLOR]        }
    In all other cases, we want the sum of all paths that start one square to the right and all paths that start one square down from where we are now:
    Java Code:
            public BigInteger pathCount(int x, int y) {
                    if (x == 0 && y == 0) return BigInteger.ZERO;
                    if (x == 0) return BigInteger.ONE;
                    if (y == 0) return BigInteger.ONE;
    [COLOR="Blue"]                return pathCount(int x - 1, y).add(pathCount(x, y - 1));
    [/COLOR]        }
    This works, but gets very slow as x and y get just a little larger. The problem is that we're visiting all these points in the middle of the grid over and over again, and each time we're recursively computing the same results. This is where memoization comes in. We want to check if we've gotten the result for a particular x and y pair before, and if so, just return that same result instead of computing it all over again. So let's store the results in an array:
    Java Code:
    public class Problem15 {
    [COLOR="Blue"]        private BigInteger[][] grid;
    [/COLOR]        ...
    
            public BigInteger pathCount(int x, int y) {
                    if (x == 0 && y == 0) return BigInteger.ZERO;
                    if (x == 0) return BigInteger.ONE;
                    if (y == 0) return BigInteger.ONE;
    [COLOR="Blue"]                if (<we have a result in our array>) { // how are we going to know?
                            return grid[x][y];
                    }
                    BigInteger result =  pathCount(int x - 1, y).add(pathCount(x, y - 1));
                    grid[x][y] = result;
                    return result;
    [/COLOR]        }
    
            ...
    }
    Now I hope it's obvious we need to initialize our array and pre-load it with a sentinel value so that when we check a location we know if it is the pre-stored sentinel or an actual result. Actual results will always be positive numbers, so we can safely use -1 as a sentinel.
    Java Code:
    ...
    public class Problem15 {
            private BigInteger[][] grid;
    [COLOR="Blue"]        private static final BigInteger SENTINEL = new BigInteger("-1");
    [/COLOR]        ...
    
            public BigInteger pathCount(int x, int y) {
                    if (x == 0 && y == 0) return BigInteger.ZERO;
                    if (x == 0) return BigInteger.ONE;
                    if (y == 0) return BigInteger.ONE;
    [COLOR="Blue"]                if (!grid[x][y].equals(SENTINEL)) {
    [/COLOR]                        return grid[x][y];
                    }
                    BigInteger result =  pathCount(int x - 1, y).add(pathCount(x, y - 1));
                    grid[x][y] = result;
                    return result;
            }
    
            ...
    
    [COLOR="Blue"]        private void run() {
    		Scanner sc = new Scanner(System.in);
    
    		System.out.print("Enter number of columns: ");
    		int cols = sc.nextInt();
    		sc.nextLine(); // clear newline character
    
    		System.out.print("Enter number of rows: ");
    		int rows = sc.nextInt();
    
    		grid = new BigInteger[cols + 1][rows + 1];
    		for (int i = 0; i <= cols; i++) {
    			for (int j = 0; j <= rows; j++) {
    				grid[i][j] = SENTINEL;
    			}
    		}
    
    		BigInteger result = pathCount(cols, rows);
    		System.out.println("There are " + result + " paths.");
    
            }
    [/COLOR]
            ...
    }
    By the way, I use a run() method so that I don't have to use static everywhere. Of course I do have to instantiate my class and invoke its run() from main().

    I gave away more of the answer than I should have, but BigInteger and memoization are complex enough without clear examples. Hope I haven't ruined things for anybody.

    -Gary-

  3. #3
    subith86 is offline Senior Member
    Join Date
    Jan 2011
    Location
    Bangalore, India
    Posts
    102
    Rep Power
    0

    Default

    Hello Iron Lion,

    At first look this doesn't seem like a recursive method. Could you please try this. I haven't tested it, but this will do I suppose. Instead of 2 ifs, i have put it in one if


    Java Code:
    if (i < 3 || j < 3) {
    	result += 1 + RecursivePathFind((i<3)? ++i:i, (j<3)? ++j:j);
    }
    return result;
    Meanwhile I have a look at your Euler Project and get back with more details;)

  4. #4
    subith86 is offline Senior Member
    Join Date
    Jan 2011
    Location
    Bangalore, India
    Posts
    102
    Rep Power
    0

    Default

    Hi,

    Just now i had a look at your question and found that the code you have written comes no where near to solving that problem. Maybe you can use mathematical equation to solve it. It is given in the below link
    A square grid path problem : Joao Ferreira

  5. #5
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    5

    Default

    Thanks for your feedback. I also tried a method based on a 21-by-21 array, which also failed to solve the problem but did so far more quickly. This one certainly seemed a lot harder than those around it, but with that mathematical explanation in mind it's now a lot more straightforward than having the computer brute-force it.

Similar Threads

  1. Replies: 3
    Last Post: 02-09-2010, 06:22 AM
  2. recursive method
    By michail in forum New To Java
    Replies: 0
    Last Post: 01-31-2010, 02:50 PM
  3. Writing a recursive method :S
    By Thousand in forum New To Java
    Replies: 1
    Last Post: 12-06-2009, 04:13 PM
  4. recursive method problem
    By melody in forum New To Java
    Replies: 1
    Last Post: 10-29-2009, 08:15 AM
  5. Recursive Method
    By bluegreen7hi in forum New To Java
    Replies: 5
    Last Post: 11-29-2007, 05:45 AM

Posting Permissions

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