javascript - 如何返回递归函数中迭代生成的字符串？

Question

我在返回一个映射到达迷宫尽头的路径的字符串时遇到问题。该函数采用字符串值的二维数组迷宫和表示迷宫起点的 2 个元素的数组(例如 [0,0])。当函数被调用一次但字符串没有重新初始化时，我返回正确的路径，因此我得到多个串联的答案。 代码:

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));

日志:“DDRR” 第二次调用时:“DDRRDDRR”

Answer 1

解决此问题的一种方法是，在仍然使用 mazeSolver.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));

也就是说，更常见和标准的方法是将答案本身作为方法参数传递:

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

}

至少有几个理由选择第二种方法:

1. 在第二种方法中，递归函数所需的所有输入都位于一个位置:参数。这比第一种方法更容易理解，第一种方法中一些输入位于参数中，一个作为对象本身的属性存储。
2. 考虑一下将 mazeSolver 分配给另一个变量时的行为:letsolver = mazeSolver。现在，solver 将数据存储在 mazeSolver 上，这是困惑且违反直觉的。