C# Recursion, "Data Structures and Algorithms". How does this program print separate routes without overwriting itself?

Question

I'm currently studying Recursion in C# from the book "Data Structures and Algorithms" by Alfred V. Aho and Jeffrey D. Ullman. Link

This problem is used to reinforce an understanding of Recursion.

We are given a labyrinth with a rectangular shape, consisting of N*M squares.

Each square is either passable or impassable. An adventurer enters the labyrinth from its top left corner (there is the entrance) and has to reach the bottom right corner of the labyrinth (there is the exit).

At each turn the adventurer can move up, down, left or right with one position and he has no right to go outside the binderies of the labyrinth, or step on impassable square. Passing through one and the same position is also forbidden (it is considered that the adventurer is lost if after a several turns he goes back to a position he has already been).

The following program uses Recursion to print all possible routes through the Labyrinth in the console.

A two-dimensional array of characters represents the labyrinth, the character ' ' (space) marks the passable positions, '*' the impassable positions and 'e' is the exit from the labyrinth.

The positions we have already visited are marked with the character 's'.

An array "path[]" is used in order to store and print the paths we have found by our recursive algorithm, each direction is recorded as so (L – left, U – up, R – right, D – down).

A counter keeps track of how many times we have moved to the next position recursively, i.e. the current depth of recursion.

class Program
{
    static char[,] lab =
    {
      {' ', ' ', ' ', '*', ' ', ' ', ' '},
      {'*', '*', ' ', '*', ' ', '*', ' '},
      {' ', ' ', ' ', ' ', ' ', ' ', ' '},
      {' ', '*', '*', '*', '*', '*', ' '},
      {' ', ' ', ' ', ' ', ' ', ' ', 'e'},
    };

    static char[] path = new char[lab.GetLength(0) * lab.GetLength(1)];
    static int position = 0;

    static void FindPath(int row, int col, char direction)
    {
        if ((col < 0) || (row < 0) ||
            (col >= lab.GetLength(1)) || (row >= lab.GetLength(0)))
        {
            // We are out of the labyrinth
            return;
        }

        // Append the direction to the path
        path[position] = direction;
        position++;

        // Check if we have found the exit
        if (lab[row, col] == 'e')
        {
            PrintPath(path, 1, position - 1);
        }

        if (lab[row, col] == ' ')
        {
            // The current cell is free. Mark it as visited
            lab[row, col] = 's';

            // Invoke recursion to explore all possible directions
            FindPath(row, col - 1, 'L'); // left
            FindPath(row - 1, col, 'U'); // up
            FindPath(row, col + 1, 'R'); // right
            FindPath(row + 1, col, 'D'); // down

            // Mark back the current cell as free
            lab[row, col] = ' ';
        }

        // Remove the last direction from the path
        position--;
    }

    static void PrintPath(char[] path, int startPos, int endPos)
    {
        Console.Write("Found path to the exit: ");
        for (int pos = startPos; pos <= endPos; pos++)
        {
            Console.Write(path[pos]);
        }
        Console.WriteLine();
    }

    static void Main()
    {
        FindPath(0, 0, 'S');
            for(int i = 0; i < path.Length; i++){
        Console.Write(path[i]);
        }
    }
}

Result:

Found path to the exit: RRDDLLDDRRRRRR
Found path to the exit: RRDDRRUURRDDDD
Found path to the exit: RRDDRRRRDD

Whilst I can grasp how Recursion is working it's way through the labyrinth, I am unable to understand how "path[]" is able to print separate arrays of directions for each route through the labyrinth without resting during the program or starting from a position that leaves off directly from the previous route.

Essentially, my understanding is that each recursion is using the same global variable (path[]), why isn't each recursion overwriting directions and how are we able to print perfect directions always starting from path[1]?

In other words, Why doesn't path[] look like this at the end: "RRDDLLDDRRRRRRRRDDRRUURRDDDDRRDDRRRRDD?.

Answer 1

In your case before making these recursive calls the position = 1. And you can imagine your stack as:

Main()->FindPath()

Imagine that in order to find exit the program made 3 recursive calls. Then the stack is:

Main()->FindPath()->FindPath()->FindPath()->FindPath()

At this point the position = 4.

After printing the result, method calls return, but before that they decrease the position by 1.

So before going for another set of recursive calls your stack is again looks like this:

Main()->FindPath()

and the position = 1.