Why is my recursive maze algorithm not back tracking?

Question

Forgive me i'm new to recursion but as far as i understand this should work, but it doesn't. I made this method that calls itself recursively when successfully found a path:

private void RandStep(Point pos)
    {       
        Collections.shuffle(Arrays.asList(directions), rand); //Incorrect, should have a local directions array. Nothing to do with the question though.
        for (int i = 0; i < directions.length;i++)
        {
            //Check if the positions are within map bounds.
            if (pos.x + directions[i].x >= 0 && pos.x + directions[i].x < width && pos.y + directions[i].y >= 0 && pos.y + directions[i].y < height)
            {
                //Check if the position is unvisited.
                if (!mazeMap[pos.x + directions[i].x][pos.y + directions[i].y].visited)
                {
                    //Break walls this tile.
                    CarvePassage(pos, directions[i]);
                    mazeMap[pos.x + directions[i].x][pos.y + directions[i].y].visited = true;
                    position.setLocation(pos.x + directions[i].x, pos.y + directions[i].y);
                    RandStep(position);
                }
            }
        }
    }

• First it randomizes an array with 4 directions.
• Then i loop through the array to find a possible direction.
• Then It checks if the direction found is valid otherwise it goes to the next direction in the array
• When it is valid it calls another method that carves the wall of the current tile and the next tile.
• It changes the current position to the next and sets it's flag to visited.
• Finally it calls itself again to make the next step.

This all works until the first time it gets stuck between visited cells or map bounds. If i understand recursion correctly it should exit this method and go to the previous run of RandStep and finish the direction loop. When it does not find any valid cells there: it again should exit and finish the loop in the previous RandStep. This should be repeated until it finished the direction loop of the very first RandStep run.

Like i said, it stops at the moment it cannot find any valid cells. It does not continue the previous methods on the recursion stack.

Answer 1

Quite simply, it's because you don't step back!

position.setLocation(pos.x + directions[i].x, pos.y + directions[i].y);
RandStep(position);

Should be something like:

position.setLocation(pos.x + directions[i].x, pos.y + directions[i].y);
RandStep(position);
position.setLocation(pos.x - directions[i].x, pos.y - directions[i].y);

As a bit of intuition, think about what happens in the base case of recursion. all tiles around you are visited, and you are at a dead end. That situation looks like:

 _
| |
|x|

(x = "you are here")

Then, position.setLocation(pos.x + directions[i].x, pos.y + directions[i].y); puts you here:

 _
|x|
| |

Then, RandStep(position); does nothing since all locations around you are explored. So the next thing you want to do is step backwards, which is accomplished by something like: position.setLocation(pos.x - directions[i].x, pos.y - directions[i].y);.