recursive labyrinth program / pathfinder

Question

This is a snippet of a code that works as a pathfinder, and it uses a recursive method. I don't quite see how it works though. So, we let the user create the labyrinth, and after he did, we start the method findRek in the main method. We check whether some field is a wall or a path that we already walked on (marked by a " - "). We want to mark every field that is not the start but is still free.

In the second paragraph, we work with the principle of recursion, checking top, down, left and right - that's were I'm lost. So the method is calling itself here, but under what circumstances does it return a "true"? Only when the field that we stand on is the goal? Plus, what happens here if we get a "false" after calling the method again with a certain direction? Does it check every direction then?

The last paragraph in the recursive method sets the field we are standing on as free since it was marked as a path before, which would always lead to a false.

private static boolean findRek(char[][] lab, int x, int y) {

if (lab [y][x] == GOAL)
  return true;
if (lab [y][x] == WALL)
  return false;
if (lab [y][x] == PATH)
  return false;
if (lab [y][x] != START)
  lab[y][x] = PATH;

if (findRek(lab, x, y-1))
  return true;
if (findRek(lab, x+1, y))
  return true;
if (findRek(lab, x, y+1))
  return true;
if (findRek(lab, x-1, y))
  return true;

lab[y][x] = FREE;
  return false;
}

...

public static void main(String[]args) {

boolean yes = findRek(lab);
if(yes) {

...

Since this was called a possible duplicate: It's not like I didn't understand recursion in genereal, but I don't quite get the operating principle of the boolean variables here.

Possible duplicate of [Understanding how recursive functions work](http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — hotzst, Dec 04 '16 at 19:12
Why? This question is specifically about boolean variables, it's not like I didn't understand recursion in general. — Borol, Dec 04 '16 at 19:16
From reading your question I gather that your problem is understanding how recursion works. — hotzst, Dec 04 '16 at 19:19

score 0 · Answer 1 · answered Dec 04 '16 at 19:20

So the method is calling itself here, but under what circumstances does it return a "true"?

Each recursion is basically taking one step forward. Once it reaches the GOAL (which takes X steps, i.e. X recursive calls), the first if statement returns true, and when a recursive call returns true, the method will also return true, so when it hit the GOAL, the entire recursion call stack will be unwound by X return true statements.

Only when the field that we stand on is the goal?

That's what triggers the unwinding, leading to the initial call returning true, i.e. path to goal was found, and the path to the goal is left marked in the maze.

Plus, what happens here if we get a "false" after calling the method again with a certain direction?

When a step forward, aka a recursive call, hits a WALL or PATH, it'll return false, indicating "wrong direction". The caller will then skip to try another direction. If all 4 directions end in "wrong direction", we're obvious on the wrong path to the goal, so the method will undo stepping to the current location and return false, so the previous step can try it's other directions. This is called backtracking.

Does it check every direction then?

Until it finds the GOAL, yes.

Thank you for your answer! So, for example, when we stand at point P, and then we head 3 steps to the right like P -> P_1 -> P_2 -> P_3, the programm returns "true" in all of these cases and marks every step, but when he hits a WALL at P_3 -> WALL, he checks the top and the bottom, but when he hits a WALL again in those cases, he goes back to P and sets it back to FREE? — Borol, Dec 04 '16 at 19:26
*"programm returns "true" in all of these cases"* If "right" is the first direction checked (it's not, but let's assume it was), and you make 3 steps to the right, then no call has returned yet, so no return of *any* `true` or `false` value has happened. It you don't understand this, then I think [hotzst might have been right](http://stackoverflow.com/questions/40962494/recursive-labyrinth-program-pathfinder/40962614?noredirect=1#comment69134362_40962494) and you don't understand recursion at all. — Andreas, Dec 04 '16 at 19:33

recursive labyrinth program / pathfinder

1 Answers1