如何避免递归实现的无交叉往返寻路算法出现栈溢出？

问题背景 #

我有一个处理二维数组索引点的函数，输入为([2,2],[6,6])这类点对，需求如下：

• 生成pathAB：从起始点A出发，随机向任一索引加2，直到到达终点B，将所有点存入数组；
• 生成pathBA：从B出发，随机向任一索引加2或减2回到A，要求pathBA既不能与pathAB的中间点交叉，也不能自交叉。

当前递归实现仅85%能成功生成路径，剩余15%会触发栈溢出，且两点距离越大，栈溢出概率越高。其中pathBA与pathAB的交叉检查是核心问题——移除检查则无栈溢出，但无法满足路径不交叉的需求。

原代码的核心问题 #

• 递归深度超限：递归依赖JS引擎的调用栈，当路径过长时，递归层数超过栈上限（通常约1000层），直接触发栈溢出。
• 暴力重试效率极低：每次路径交叉或越界就清空路径从头递归，路径越长，重试次数指数级上升，进一步加剧栈溢出风险。
• 交叉检查效率差：用forEach遍历数组对比字符串化的坐标，时间复杂度O(n)，每次检查拖慢执行速度，增加重试概率。

优化方案 #

核心优化方向 #

• 用迭代循环替代递归，手动维护路径状态，彻底避免栈溢出；
• 用Set存储已访问/禁止点，将交叉检查的时间复杂度降到O(1)；
• 实现路径回溯机制，走不通时回退到上一步尝试其他方向，而非清空路径重来；
• 约束pathBA的移动范围，利用pathAB的边界减少交叉概率。

优化后的完整代码 #

// 工具函数：生成指定范围的随机整数
function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 生成pathAB：迭代实现，无栈溢出风险
function generatePathAB(start, end) {
  const path = [start.slice()];
  let current = start.slice();
  
  while (current[0] !== end[0] || current[1] !== end[1]) {
    // 只允许向未到达终点的方向移动，避免越界重试
    const availableDirs = [];
    if (current[0] < end[0]) availableDirs.push(0); // x方向可移动
    if (current[1] < end[1]) availableDirs.push(1); // y方向可移动
    
    // 理论上不会触发（因为start和end坐标差为偶数，步长2）
    if (availableDirs.length === 0) return generatePathAB(start, end);
    
    const dir = availableDirs[randomInt(0, availableDirs.length - 1)];
    current[dir] += 2;
    path.push(current.slice());
  }
  
  return path;
}

// 生成pathBA：迭代+回溯+集合检查，避免栈溢出与路径交叉
function generatePathBA(start, end, forbiddenPoints) {
  const path = [start.slice()];
  // Set存储已访问点，O(1)快速查询
  const visited = new Set([start.toString()]);
  // 记录每一步剩余的可选方向，用于回溯
  const dirHistory = [];
  
  while (true) {
    const current = path[path.length - 1];
    
    // 到达终点，返回路径
    if (current[0] === end[0] && current[1] === end[1]) return path;
    
    // 收集所有合法的移动方向：不越界、未访问、不在禁止列表
    const possibleMoves = [
      [current[0] + 2, current[1]],
      [current[0] - 2, current[1]],
      [current[0], current[1] + 2],
      [current[0], current[1] - 2]
    ];
    const availableDirs = [];
    
    for (let i = 0; i < possibleMoves.length; i++) {
      const [x, y] = possibleMoves[i];
      const key = `${x},${y}`;
      // 边界约束：和原代码一致，数组最大索引为8
      if (x >= 0 && x <= 8 && y >= 0 && y <= 8) {
        if (!visited.has(key) && !forbiddenPoints.has(key)) {
          availableDirs.push(i);
        }
      }
    }
    
    if (availableDirs.length > 0) {
      // 随机选择一个合法方向
      const dirIdx = randomInt(0, availableDirs.length - 1);
      const chosenDir = availableDirs[dirIdx];
      const [newX, newY] = possibleMoves[chosenDir];
      const newPoint = [newX, newY];
      
      // 更新路径与已访问集合
      path.push(newPoint);
      visited.add(newPoint.toString());
      // 保存剩余可选方向（回溯时排除已选方向）
      dirHistory.push(availableDirs.filter(idx => idx !== chosenDir));
    } else {
      // 无路可走，回溯到上一步
      const lastPoint = path.pop();
      visited.delete(lastPoint.toString());
      dirHistory.pop();
      
      // 回溯到起点仍无路可走，重新生成（极端情况）
      if (path.length === 0) {
        return generatePathBA(start, end, forbiddenPoints);
      }
    }
  }
}

// 使用示例
const startPoint = [2, 2];
const endPoint = [6, 6];

const pathAB = generatePathAB(startPoint, endPoint);
// 提取pathAB的中间点作为禁止点（排除起点和终点）
const forbiddenSet = new Set(
  pathAB.slice(1, pathAB.length - 1).map(p => p.toString())
);
const pathBA = generatePathBA(endPoint, startPoint, forbiddenSet);

console.log("pathAB:", pathAB);
console.log("pathBA:", pathBA);

优化效果说明 #

1. 彻底解决栈溢出：迭代实现不依赖调用栈，支持任意长度的路径生成；
2. 路径检查效率暴增：Set的O(1)查询替代原代码的O(n)遍历，大幅减少检查耗时；
3. 避免无效重试：回溯机制仅回退到上一步，而非清空整个路径，提升生成成功率；
4. 路径生成更可靠：pathAB生成时仅允许合法方向，避免原代码中越界重试的情况。

内容的提问来源于stack exchange，提问作者HeyHannibal