What is wrong with my Java recursive function?

Question

I'm trying to write a relatively straightforward recursive program in Java to compute all the possible ways to traverse a 4x4 matrix (not necessarily traveling through every spot), starting at the top left and ending in the bottom right spaces. I use a 2-D array to do this, marking off visited spaces with "1"s as I go.

It's been a while since I've worked recursively and I can't seem to get the output I expect. The output from the code below is "2" - obviously, the result should be much higher. I know there's something tiny I'm overlooking. Can someone tell me what it is?

public static void main(String[] args) {
    int[][] matrix = new int[4][4];
    int result = moveRobot(matrix, 0, 0);
    System.out.print(result + "");
}

public static int moveRobot(int[][] matrix, int x, int y) {
    if (x == 3 && y == 3) {
        return 1;
    } else if (x < 0 || y < 0 || x > 3 || y > 3) {
        return 0;
    } else if (matrix[x][y] == 1) {
        return 0;
    } else {
        matrix[x][y] = 1;
        return moveRobot(matrix, x, y+1) + moveRobot(matrix, x+1, y) + moveRobot(matrix, x, y-1) +
                moveRobot(matrix, x-1, y);
    }
}

Why should the result be much higher? You return 1, 0 or the sums of 1 and 0(s). 2 seems like a reasonable total for 2 1(s) and any number of 0(s). — Elliott Frisch
– Elliott Frisch, Commented Jul 11, 2016 at 22:41
Because there are more than 2 total possible ways to traverse a 4x4 matrix. The answer I'm getting isn't the solution to the problem. — snydermb
– snydermb, Commented Jul 11, 2016 at 22:44

Jack · Accepted Answer · 2016-07-11 22:44:11Z

1

The problem is that the matrix is not copied but passed by value of the reference to it. Every time you modify it such in matrix[x][y] = 1 other successive code paths will see the modification instead that working on an unmodified state.

For example here:

moveRobot(matrix, x, y+1) + moveRobot(matrix, x+1, y)

Entering the first call will modify matrix, so in second moveRobot call you'd end up with 1 in matrix[x][y+1] while that's not what you want.

answered Jul 11, 2016 at 22:44

Jack

134k33 gold badges252 silver badges349 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

snydermb Over a year ago

Thanks for the response. I thought that might be the case. What is another way I can keep track of visited spots in the matrix as I go otherwise?

Jack Over a year ago

Just creating a copy of the matrix is fine. You could have an helper method like int[][] copy(int[][] matrix) that you can use every time you need to pass the current state to a recursive call. Remember that you need a copy for each invocation, just one is not enough.

snydermb Over a year ago

Yep, just did the same thing and figured it out. I'm dumb and forgot how passing works in Java. Thanks again man!

Collectives™ on Stack Overflow

What is wrong with my Java recursive function?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related