C# 递归， "Data Structures and Algorithms"。该程序如何在不覆盖自身的情况下打印单独的路线？

Question

我目前正在学习 Alfred V. Aho 和 Jeffrey D. Ullman 合着的“数据结构和算法”一书中的 C# 递归。 Link

这个问题用来加深对递归的理解。

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

以下程序使用递归在控制台中打印通过迷宫的所有可能路径。

一个二维字符数组代表迷宫，字符' '(空格)表示可以通过的位置，'*'表示不能通过的位置，'e'是迷宫的导出。

我们已经访问过的位置标有字符“s”。

数组“path[]”用于存储和打印我们通过递归算法找到的路径，每个方向都这样记录(L – left, U – up, R – right, D – down ).

计数器会记录我们递归移动到下一个位置的次数，即当前的递归深度。

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

结果:

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

虽然我可以理解递归是如何在迷宫中工作的，但我无法理解“path[]”如何能够在程序期间不休息或从一个直接偏离之前路线的位置。

基本上，我的理解是每个递归都使用相同的全局变量 (path[])，为什么每个递归都不会覆盖方向，我们如何能够始终从 path[1] 开始打印完美的方向？

换句话说，为什么 path[] 最后看起来不像这样:“RRDDLLDDDRRRRRRRRDDRRUURRDDDDRRDDRRRRDD?。

Answer 1

在进行这些递归调用之前，position = 1。您可以将堆栈想象为:

Main()->FindPath()

想象一下，为了找到导出，程序进行了 3 次递归调用。那么堆栈是:

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

此时position = 4.

打印结果后，方法调用返回，但在此之前它们将位置减 1。

所以在进行另一组递归调用之前，您的堆栈再次看起来像这样:

Main()->FindPath()

并且位置 = 1。