返回函数返回到主函数而不是调用方

Question

只是想知道...

void mazeTraversal(char maze[12][12], int x, int y)
{
if (maze[x + 1][y] == '.')
    mazeTraversal(maze, ++x, y);
if (maze[x][y + 1] == '.')
    mazeTraversal(maze, x, ++y);
if (maze[x - 1][y] == '.')
    mazeTraversal(maze, --x, y);
if (maze[x][y - 1] == '.')
    mazeTraversal(maze, x, --y);
   return;
}

当我遇到死胡同时，我是否应该恢复到调用的上一个实例，而不是直接回到主函数？如果我有什么不对劲的地方，请告诉我。

Answer 1

以下地址使用返回值捕获"正确路径"信息并提供基本情况条件。但是，原始代码的另一个关键问题是使用++/--，这会对相应的变量产生副作用。出于这个原因，下面的代码避开了这些运算符。

---

执行此操作的主要方法是返回一个值 - 例如，如果此路径导致 true 和结束，否则返回 false。

然后，非常原始的转换将如下所示。请注意基本情况的添加 - 这意味着我们可以停止递归。返回 True，以便以前的调用方也知道他们可以停止查找，并且函数堆栈将很快展开回"main"。

bool mazeTraversal(char maze[12][12], int x, int y) {
  // This is the BASE CASE and means WE ARE DONE LOOKING
  if (maze[x][y] == 'X') return true; // found end!
  if (maze[x + 1][y] == '.')
    if (mazeTraversal(maze, x + 1, y)) return true;
  if (maze[x][y + 1] == '.')
     if (mazeTraversal(maze, x, y + 1)) return true;
  if (maze[x - 1][y] == '.')
     if (mazeTraversal(maze, x - 1, y)) return true;
  if (maze[x][y - 1] == '.')
     if (mazeTraversal(maze, x, y - 1)) return true;
  return false; // didn't find any valid path from here
}

请注意，我删除了++/--以避免奇怪的副作用。

但是，我们可以做得更好，并清理一些代码。关键的区别在于每个递归调用都会检查当前位置 - 而不是其邻居的位置。

bool mazeTraversal(char maze[12][12], int x, int y) {
  if (maze[x][y] == 'X')
    return true; // found end!
  if (maze[x][y] == '.') {
    // we are still on a path - see where exploration leads!
    if (mazeTraversal(maze, x + 1, y)) return true;
    if (mazeTraversal(maze, x, y + 1)) return true;
    if (mazeTraversal(maze, x - 1, y)) return true;
    if (mazeTraversal(maze, x, y - 1)) return true;
  }
  // Didn't find any valid path from here -
  // maybe "here" is a wall!
  return false;
}

最终，您可能希望在找到的路径上执行其他操作（即它读取"return true"的位置），例如记录当前位置。

另请注意，根据语言的不同，if (mazeTraversal..) return true的东西也可以"清理"。在 C 语言中，考虑使用短路||运算符。然后我们可以将最终情况缩短为：

int leadsToEnd =
       (maze[x][y] == 'X')      // at end
    || (maze[x][y] == '.')      // or not end ..
       && (mazeTraversal(maze, x + 1, y)   // but may lead to end
           || mazeTraversal(maze, x, y + 1)
           || mazeTraversal(maze, x - 1, y) 
           || mazeTraversal(maze, x, y - 1));

因此，整个函数有效地变得return leadsToEnd（根据需要替换上述表达式）。当然，你必须决定哪种方法——后一个例子可以说是过于聪明——或者这种方法的混合对你来说最有意义。

Answer 2

就像你现在一样，当你陷入死胡同时，你就会回来。 这是正确的，因为您将备份到上一个调用，然后选择下一个路径。 遍历所有可能的路径后，顶级调用将返回。