Recursive method infinitely looping

[Iron Lion]

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

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?

[gcalvin]

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.

[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.

        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:

        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:

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.

...
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-

[subith86]

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

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

[subith86]

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

[Iron Lion]

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.