How do I return a string that is generated by iteration in a recursive function?

user_18319197 0
Viewed 44

I am having an issue returning a string that maps the path taken to get to the end of a maze. The function takes a 2-d array maze of string values and an array of 2 elements that represent the starting point of the maze(eg. [0,0]). I am returning the correct path when the function is called once but the string is not reinitialized so I get multiple answers concatenated. Code:

function mazeSolver(maze, index = [0, 0]) {
  if (typeof mazeSolver.answer == "undefined") {
    mazeSolver.answer = "";
  }
  const pointer = () => maze[index[0]][index[1]];
  if (index[1] < maze[0].length - 1) {
    index[1] += 1;
    if (pointer() === " " || pointer() === "e") {
      mazeSolver.answer += "R";
      if (pointer() === "e") return mazeSolver.answer;
      return mazeSolver(maze, index);
    } else {
      if (index[0] < maze.length - 1) {
        index[1] -= 1;
        index[0] += 1;
        if (pointer() === " " || pointer() === "e") {
          mazeSolver.answer += "D";
          if (pointer() === "e") return mazeSolver.answer;
          return mazeSolver(maze, index);
        }
      }
    }
  } else if (index[0] < maze.length - 1) {
    index[0] += 1;
    if (pointer() === " " || pointer() === "e") {
      mazeSolver.answer += "D";
      if (pointer() === "e") return mazeSolver.answer;
      return mazeSolver(maze, index);
    }
  }
}
const mySmallMaze = [
  [" ", "*", " "],
  [" ", "*", " "],
  [" ", " ", "e"],
];
console.log(mazeSolver(mySmallMaze));

logs: "DDRR" on second call: "DDRRDDRR"

javascript
1 Answers

One way to solve this, while still using your mazeSolver.answer approach, is to pass an extra parameter which tracks whether we're in a recursive call or not. If not, we reset the answer:

function mazeSolver(maze, index = [0, 0], top_level_call = true) {
  if (top_level_call) {
    mazeSolver.answer = "";
  }
  const pointer = () => maze[index[0]][index[1]];
  if (index[1] < maze[0].length - 1) {
    index[1] += 1;
    if (pointer() === " " || pointer() === "e") {
      mazeSolver.answer += "R";
      if (pointer() === "e") return mazeSolver.answer;
      return mazeSolver(maze, index, false);
    } else {
      if (index[0] < maze.length - 1) {
        index[1] -= 1;
        index[0] += 1;
        if (pointer() === " " || pointer() === "e") {
          mazeSolver.answer += "D";
          if (pointer() === "e") return mazeSolver.answer;
          return mazeSolver(maze, index, false);
        }
      }
    }
  } else if (index[0] < maze.length - 1) {
    index[0] += 1;
    if (pointer() === " " || pointer() === "e") {
      mazeSolver.answer += "D";
      if (pointer() === "e") return mazeSolver.answer;
      return mazeSolver(maze, index, false);
    }
  }
}
const mySmallMaze = [
  [" ", "*", " "],
  [" ", "*", " "],
  [" ", " ", "e"],
];
console.log(mazeSolver(mySmallMaze));

That said, a more common and standard approach would be to just pass around the answer itself as a method parameter:

function mazeSolver(maze, index = [0, 0], answer = "") {
    ...
    answer += "R";
    ...
    return mazeSolver(maze, index, answer);
    ...
    return answer

}

There are at least a couple reasons to prefer the second approach:

  1. In the second approach, all the inputs needed by the recursive function are in one place: parameters. This is easier to understand than the first approach, where some inputs are in the parameters and one is stored as a property on the object itself.
  2. Consider the behavior if we assign mazeSolver to another variable: let solver = mazeSolver. Now solver is storing data on mazeSolver, which is messy and counterintuitive.
user_20456110
Related