java - 为什么我的递归迷宫算法不回溯？

Question

请原谅我是递归的新手，但据我所知，这应该可行，但事实并非如此。我做了这个方法，当成功找到路径时递归调用自身:

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

• 首先，它随机化一个具有 4 个方向的数组。
• 然后我遍历数组以找到可能的方向。
• 然后检查找到的方向是否有效，否则转到数组中的下一个方向
• 当它有效时，它会调用另一个方法来雕刻当前瓷砖和下一个瓷砖的墙壁。
• 它将当前位置更改为下一个位置并将其标志设置为已访问。
• 最后它再次调用自己进行下一步。

这一切都有效，直到它第一次卡在已访问的单元格或 map 边界之间。如果我正确理解递归，它应该退出此方法并转到之前运行的 RandStep 并完成方向循环。当它在那里找不到任何有效的单元格时:它应该再次退出并完成前面的 RandStep 中的循环。这应该重复，直到它完成第一个 RandStep 运行的方向循环。

就像我说的，它会在找不到任何有效单元格的那一刻停止。它不会在递归堆栈上继续以前的方法。

Answer 1

很简单，因为你没有后退!

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);
RandStep(position);
position.setLocation(pos.x - directions[i].x, pos.y - directions[i].y);

作为一点直觉，想想在递归的基本情况下会发生什么。你周围的所有瓷砖都被访问过，你在死胡同里。这种情况看起来像:

 _
| |
|x|

( x = "你在这里")

然后，position.setLocation(pos.x + directions[i].x, pos.y + directions[i].y);把你放在这里:

 _
|x|
| |

然后，RandStep(position); 什么都不做，因为你周围的所有位置都被探索过了。所以接下来你要做的是向后退一步，这是通过类似这样的事情来完成的:position.setLocation(pos.x - directions[i].x, pos.y - directions[i].y); .