Advanced Recursion in Java

Question

I just can't get the hang of recursion, especially with complicated examples. I would really appreciate it if someone would take some time to explain it. I literally have 4 pieces of paper all filled with me tracing this function, but I have no idea how to put it together.

public static String shortestPath(int x, int y, int tX, int tY,boolean blocked[][]) {

        if(x>blocked.length-1 || y>blocked[0].length-1 || x<0 || y<0 )
            return null;
        if(blocked[x][y]==true)
            return null;
        if(x==tX && y==tY)
            return "";

        String paths[]=new String[4];
        blocked[x][y]=true; //this just means this coordinate is blocked, so dont use it
        paths[0]=shortestPath(x, y+1, tX, tY, blocked);
        paths[1]=shortestPath(x, y-1, tX, tY, blocked);
        paths[2]=shortestPath(x+1, y, tX, tY, blocked);
        paths[3]=shortestPath(x-1, y, tX, tY, blocked);
        blocked[x][y] = false;
        int result=findShortestString(paths, 0, 3); 
//findShortestString just takes an array of strings, 
//with 0 being the lo index and 3 being the hi, 
//and returns the index that contains the string with the shortest length.
        //5
        if(paths[result]==null)
           return null;
        else{

           if(result==0)
                return 'N' + paths[result];
           if(result==1)
                return 'S' + paths[result];
           if(result==2)
                return 'E' + paths[result];
           if(result==3)
                return 'W' + paths[result];}

        return paths[result];

So what this code does is, given an x and y parameter, it tells you the shortest combination of moves you would have to make (NSWE for north, south, west, east) in order to reach the tX and tY parameters. The code works perfectly, but I have no idea how.

When I try to trace what paths[0] computes, it always comes out to null, because y will always keep incrementing until it goes out of bounds, in which it returns null. This is the same case for paths[1] [2] and [3], they all return to null, don't they? So then how the heck is this function working?

possible duplicate of Understanding recursion in Java a little better — user207421
– user207421, Commented Nov 13, 2010 at 8:50

Phil · Accepted Answer · 2010-11-13 02:17:30Z

First try it with a trivially small example - a 1x1 grid with no blocked cells. As expected, there are no moves to be made. x == tX and y == tY so you return empty string. Good so far.

Now look at a 2x2 grid where you are in the NW corner and the destination is NE.

| @ | ^ |
| o | o |

When you try to go east and set paths[0] it invokes shortestPath, blocking off your current cell and setting your new location to the one below you. Now you have

| X | ^ |
| @ | o |

In that invocation, it's going to try to go N, W, S and E. Ignore for simplicity that going east happens before west, so we can finish up the other 3 directions right away - they all invoke again shortestPath on an invalid location (2 out of bounds, 1 you've been to) and return null immediately. You are left going east with a new grid and location like this:

| X | ^ |
| X | @ |

Again, 3 of the directions return null. Only north will give you the end result you want. When you try to go there, you once again invoke shortestPath which immediately returns empty string because the board now looks like this:

| X | @^ |
| X | X  |

Now we get to wrap up the call stack:

Because paths[1] was empty string and the other 3 were null, result is 1 (I assume that's how your string function works). So you return "N" to the previous call.
The previous call is going to show that paths[0] == null, paths[1] == null, paths[3] == null but critically paths[2] is "N". Therefore result will be 2, and you will return "EN" to the earlier call.

Since now you are returning to the very first invocation of shortestPath, that wraps up the first choice we made - going south from the start position. But we also had 1 more choice - go east. So you follow that tree out and it is simply "".

Then comes the final step, where you see which string is smaller and get that "" is of course smaller than "EN". So result is 2, and therefore you prefix the string with "E", and "E" is your final answer.

Now use that to figure out the larger examples. It helps to draw a decision tree and the state of the board at each node. And as you get to the leaves, draw arrows going back up to the parent node representing return values. That will help immensely.

Thanks man, this really helped. Do you/anyone have any good readings on recursion?

mbeckish · Accepted Answer · 2010-11-13 02:18:12Z

Trying to guess what you're thinking -

You might be picturing 4 execution paths:

path 0: shortestPath(x, y+1, tX, tY, blocked) -> shortestPath(x, y+1, tX, tY, blocked) ->...

path 1: shortestPath(x, y-1, tX, tY, blocked) -> shortestPath(x, y-1, tX, tY, blocked) ->...

path 2: shortestPath(x+1, y, tX, tY, blocked) -> shortestPath(x+1, y, tX, tY, blocked) ->...

path 3: shortestPath(x-1, y, tX, tY, blocked) -> shortestPath(x-1, y, tX, tY, blocked) ->...

In reality, the execution paths make a tree. Each call to shortestPath spawns 4 more calls to shortestPath, a "path0" call, a "path1" call, a "path2" call, and a "path3" call.

So, you will get one execution path that is path0, path0, path0... that will return null.

But, most of the paths will be a combination of different calls.

When the recursion returns to the first shortestPath call, paths[0] will contain the shortest path whose FIRST move was shortestPath(x, y+1, tX, tY, blocked), path[1] the shortest path whose FIRST move was shortestPath(x, y-1, tX, tY, blocked), etc.

olivervbk · Accepted Answer · 2010-11-13 02:33:11Z

It's not that complicated.

This part checked if x or y parameters are valid(either in boundary or not blocked)

if(x>blocked.length-1 || y>blocked[0].length-1 || x<0 || y<0 )
   return null;
if(blocked[x][y]==true)
   return null;

Here it is checked if the position arrived at the destination

if(x==tX && y==tY)
   return "";

Now to the recursive part, this function recurses into four other functions, each for an available NSWE direction relative to the current position:

String paths[]=new String[4];
blocked[x][y]=true; //this just means this coordinate is blocked, so dont use it
paths[0]=shortestPath(x, y+1, tX, tY, blocked);
paths[1]=shortestPath(x, y-1, tX, tY, blocked);
paths[2]=shortestPath(x+1, y, tX, tY, blocked);
paths[3]=shortestPath(x-1, y, tX, tY, blocked);
blocked[x][y] = false;
int result=findShortestString(paths, 0, 3);

Each of the route found by the recursed functions is then compared to find the shortest path/string of directions available.

findShortestString() probably returns null if every string is null, so the destination can not be reached from the originating position of that recursion.

The current position of the recursion is marked as blocked so the algorithm does not go back to a position visited before.

if(paths[result]==null)
    return null;

This checks if findShortestString did not find any valid path.

At the end the path found relative to the current position in the recursion is appended to the direction of the recursed call which found the shortest path.

Example: Lets say that a map has only one valid path to a destination, all other positions are bocked. The starting position is [0][0] and the destination is [1][1](x+1 = N, y+1 = E) MAP:

(y-line increases upwards, x-column increases rightwards)
0D
SX

S-start
X-blocked
0-not blocked
D-destination

First call:

-x,y are within boundaries and are not the destination
-blocks current positions([0][0])
-calls function for y = y+1 -> is blocked (returns NULL)
-calls function for y = y-1 -> out of boundaries (returns NULL)
-calls function for x = x+1 -> path is ok

RECURSION:

-blocks current position[1][0]
-calls function for y = y+1 -> Destination!(returns "")
-calls function for y = y-1 -> out of boundaries(returns NULL)
-calls function for x = x+1 -> out of boundaries(returns NULL)
-calls function for x = x-1 -> blocked(returns NULL) (this would be the starting position)
Since paths[0] has the shortest string("") and the result is 'N'+""

(back to the first iteration)

-calls function for x = x-1 -> out of boundaries(returns NULL)

Since paths[2] has the shortest string, the result is 'E'+'N'. Which is correct.

Since the y = y+1 is always called first, the recursion runs until it goes out of boundary. Then it will test the other positions around the last position and so forth.

Collectives™ on Stack Overflow

Advanced Recursion in Java

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related