递归函数中哪里需要 return 语句？

Question

我在 topcoder 和迷宫求解器的解决方案中阅读了这篇关于递归的文章，我不明白为什么 "if exploreMaze()" 语句之后需要 "return true" 语句，因为它们已经在后面给出了基本条件。

function exploreMaze(maze[][],x,y)
{
  // If the current position is off the grid, then
  // we can't keep going on this path
  if y>8 or y<1 or x<'A' or x>'H' then return false

  // If the current position is a '*', then we
  // can't continue down this path
  if maze[x][y]=='*' then return false

  // If the current position is an 'E', then 
  // we're at the end, so the maze is solveable.enter code here
  if maze[x][y]=='E' then return true

  // Otherwise, keep exploring by trying each possible
  // next decision from this point.  If any of the options
  // allow us to solve the maze, then return true.  We don't
  // have to worry about going off the grid or through a wall - 
  // we can trust our recursive call to handle those possibilities
  // correctly.

  if exploreMaze(maze,x,y-1) then return true  // search up
  if exploreMaze(maze,x,y+1) then return true  // search down
  if exploreMaze(maze,x-1,y) then return true  // search left
  if exploreMaze(maze,x+1,y) then return true  // search right

  // None of the options worked, so we can't solve the maze
  // using this path.

  return false
}

Answer 1

看起来迷宫是作为文本块创建的。 * 用于表示墙，或越界。字母'E'用于表示迷宫的出口。它可能看起来像这样：

********************E**
*......*......*......**
*.********.*******.****
*.....*......*........*
*.*************.*****.*
*..*............*****.*
***********************

从 y<1 y>8 行来看，尺寸应为 8 高，但您明白了。当位置为字母'E'时，则找到出口，解迷宫。 'A' 和 'H' 用于表示某种宽度。我不太明白，但这是同一个想法。

递归是这样工作的。以我的起点为例，假设 x=7,y=6。如果它是出口，那么我们就成功了。如果它在墙上，我们就失败了。如果超出范围，我们就失败了，现在检查我周围的所有四个位置，然后做同样的事情。如果这四个位置中的任何一个找到出口，那么我们就成功了。

如果迷宫是可解的，那么我们得到'true'，如果一个分支是可解的，那么我们得到真。如果迷宫无法从给定的起始位置解决，则返回 false，如果分支没有通向出口，则返回 false。

Answer 2

基本案例在这里：

if maze[x][y]=='E' then return true

–如果你到达了终点，你成功地解决了迷宫，因此迷宫是可解的，你returntrue这么说

现在如果你到达了一些点，这还不是终点，并递归探索迷宫的其余部分（这就是if指令中发生的事情），并且您从递归调用中得到了 true，然后该递归调用设法到达了端点。因此迷宫是可解的 – return true.

注意

提供的代码不正确：它无法正确处理无法解决的迷宫。

如果迷宫无法解开，要么是因为没有'E'位置：

******
*....*
******

或缺少适当的路径：

**********
*........*
*.********
*......*E*
**********

代码将重复'forever'直到堆栈溢出，然后崩溃。

递归函数中哪里需要 return 语句？

Where is return statement required in recursive functions?

algorithm

recursion

depth-first-search