Где оператор return требуется в рекурсивных функциях? - PullRequest
Новая
       14

Где оператор return требуется в рекурсивных функциях?

0 голосов
/ 29 марта 2019

Я читал эту статью о рекурсии в topcoder и в решении для решателя лабиринтов, я не понимаю, почему требуется выражение «возвращать истину» после операторов «if exploreMaze ()», так как они уже даны после базовогоусловия. 

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
}

Ответы [ 2 ]

0 голосов
/ 29 марта 2019

Базовый случай здесь: 

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

- если вы достигли конечной точки, вам удалось решить лабиринт, следовательно, лабиринт разрешим, и вы возвращаете true, чтобы сказать это.

Теперь, если вы достигли некоторой точки, которая еще не является конечной точкой, и рекурсивно исследовали остальную часть лабиринта (это то, что произошло в инструкции if), и вы получили trueиз рекурсивного вызова этот рекурсивный вызов достиг конечной точки.Следовательно, лабиринт является разрешимым - return true.

NOTE

Представленный код является неверным : он не может правильно обрабатывать неразрешимоелабиринт.

Если лабиринт не разрешим, либо из-за отсутствия позиции 'E': 

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

, либо из-за отсутствия подходящего пути: 

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

код будет повторяться «вечно» до тех пор, пока стек не переполнится, а затем завершится сбоем.

0 голосов
/ 29 марта 2019

Похоже, лабиринт создан как текстовый блок. * используется для обозначения стены или за ее пределами. Буква «Е» используется для обозначения выхода из лабиринта. Вероятно, это выглядело так: 

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

Из строки y <1 y> 8 размеры должны быть 8 высотой, но вы поняли идею. Когда в позиции находится буква «Е», то выход найден, и лабиринт решен. «A» и «H» используются для обозначения некоторой ширины. Я не совсем понимаю, но это та же идея.

Рекурсия работает следующим образом. Возьми мою отправную точку, скажем, х = 7, у = 6. Если это выход, то мы успешны. Если это на стене, мы потерпели неудачу. если это выходит за границы, мы потерпели неудачу, теперь проверьте все четыре местоположения вокруг меня и сделайте то же самое. Если какое-либо из этих четырех мест нашло выход, значит, мы успешны.

Если лабиринт разрешим, тогда мы получим 'true', если ветвь разрешима, тогда мы получим true. Если лабиринт не может быть разрешен с заданной начальной позиции, возвращается false, а если ветвь не приводит к выходу, возвращается false.

...