Results 1 to 5 of 5
 01222011, 06:14 PM #1Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 5
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 } }
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; 01222011 at 06:30 PM.
 01232011, 03:20 AM #2Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 5
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]
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] }
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] }
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] } ... }
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] ... }
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
 01232011, 07:27 AM #3Senior Member
 Join Date
 Jan 2011
 Location
 Bangalore, India
 Posts
 102
 Rep Power
 0
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;
 01232011, 07:41 AM #4Senior Member
 Join Date
 Jan 2011
 Location
 Bangalore, India
 Posts
 102
 Rep Power
 0
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
 01232011, 09:58 AM #5Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 5
Thanks for your feedback. I also tried a method based on a 21by21 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 bruteforce it.
Similar Threads

Java class HashIt with a static recursive method and a static iterative method
By kezkez in forum New To JavaReplies: 3Last Post: 02092010, 06:22 AM 
recursive method
By michail in forum New To JavaReplies: 0Last Post: 01312010, 02:50 PM 
Writing a recursive method :S
By Thousand in forum New To JavaReplies: 1Last Post: 12062009, 04:13 PM 
recursive method problem
By melody in forum New To JavaReplies: 1Last Post: 10292009, 08:15 AM 
Recursive Method
By bluegreen7hi in forum New To JavaReplies: 5Last Post: 11292007, 05:45 AM
Bookmarks