如何在JavaScript中规避数独生成递归的栈溢出问题

我正在开发一个唯一解数独谜题生成器，核心逻辑是：从完整数独解中通过Math.floor(Math.Random()*X)随机移除X个格子的数字，随后验证谜题是否存在唯一解。如果不满足唯一解，就基于同一个完整解重新生成。大部分场景下程序能正常运行，但少数情况会因为递归调用次数过多触发栈溢出。

试过异步递归+try{}catch(){}finally{}的方案，但存在两个问题：找到有效谜题时无法停止递归，且栈溢出时无法打印错误信息。现有代码如下：

async function fCreatePuzzle(solution) {
    let refere = []
    puzzleTries++
    for (let i = 0; i <= 25 + difficulty - 1; i++) {
      refere[i] = getRandomLetterAndNumber(refere)
    }
    for (let i = 0; i <= refere.length - 1; i++) {
      containddd[refere[i]].Value = null
    }
    if (fTestSolve(solution) == false) {
      for (key in containddd) {
        fChangeSudokuValAdmin(key, containddd[key].Value)
      }
    } else {
      if (puzzleTries >= 5500) {
        LoadModalText.innerText = "Could not load puzzle with " + difficulty.toString() + " as the difficulty."
        console.log("after " + puzzleTries + " attempts, we could not make a puzzle with " + difficulty.toString() + " as the difficulty. ")
        difficulty = difficulty >= 0 && difficulty - 2 >= 0 && difficulty - 2 || 0
        console.log("Lowering difficulty to " + (difficulty).toString() + " to try to create a 1 solution puzzle")
        setTimeout(function(){LoadModalText.innerText = "Lowering difficulty to " + (difficulty).toString() + " to prevent overflow errors."},2000)
        puzzleTries = 0
        setTimeout(function(){LoadModalText.innerText = "Loading Puzzle..."},1750)
      }
      resetTest(solution)
      fCreatePuzzle(solution)
    }
    return puzzleTries
  }

function InitialiseGame() {
    loadingModal.show();
    Spinner.classList.add("spinner-border","spinner-border-sm")
    LoadModalText.innerText = "Generating Sudoku Solution..."
    setTimeout(function(){
      Stime = new Date()
      True_Solution = setupSudokuSolution()
      LoadModalText.innerText = "Generating Sudoku Puzzle..."
      async function run(){
        try {
           return await fCreatePuzzle(True_Solution)
        } catch (e) {
          console.log(e)
        } finally {
          
          run()
        }
      }
      let what = run()
      number_Chosen = null
      LoadModalText.innerText = "Puzzle Generated Successfully!"
      Spinner.classList.remove("spinner-border","spinner-border-sm")
      setTimeout(function(){loadingModal.hide()},2000)
    },200)
}

问题根源分析 #

1. 同步递归栈累积：fCreatePuzzle每次验证失败就直接递归调用自己，调用次数超过浏览器栈容量时就会触发栈溢出。
2. 异步递归逻辑错误：run函数在finally里无条件调用run()，导致找到有效谜题后仍会无限循环，无法终止。
3. 错误捕获失效：同步递归的栈溢出错误会直接抛出，无法被外层异步try/catch捕获。

解决方案 #

方案1：递归改迭代（最可靠） #

用循环+自定义逻辑代替递归调用，彻底避免调用栈累积，无论尝试多少次都不会触发栈溢出。

修改后的fCreatePuzzle：

async function fCreatePuzzle(solution) {
  while (true) {
    puzzleTries++;
    let refere = [];
    // 生成要移除的格子列表
    for (let i = 0; i <= 25 + difficulty - 1; i++) {
      refere[i] = getRandomLetterAndNumber(refere);
    }
    // 移除数字
    for (let i = 0; i <= refere.length - 1; i++) {
      containddd[refere[i]].Value = null;
    }
    // 验证唯一解
    if (fTestSolve(solution)) {
      // 检查尝试次数是否超限
      if (puzzleTries >= 5500) {
        LoadModalText.innerText = `无法生成难度为${difficulty}的谜题`;
        console.log(`尝试${puzzleTries}次后，仍无法生成难度${difficulty}的唯一解谜题`);
        // 降低难度
        difficulty = Math.max(difficulty - 2, 0);
        console.log(`将难度降至${difficulty}重新尝试`);
        setTimeout(() => {
          LoadModalText.innerText = `降低难度至${difficulty}以避免溢出错误`;
        }, 2000);
        puzzleTries = 0;
        setTimeout(() => {
          LoadModalText.innerText = "正在加载谜题...";
        }, 1750);
      } else {
        // 生成成功，终止循环
        resetTest(solution);
        return puzzleTries;
      }
    } else {
      // 验证失败，恢复格子数值，继续循环
      for (const key in containddd) {
        fChangeSudokuValAdmin(key, containddd[key].Value);
      }
      resetTest(solution);
    }
  }
}

修改后的InitialiseGame：

function InitialiseGame() {
  loadingModal.show();
  Spinner.classList.add("spinner-border", "spinner-border-sm");
  LoadModalText.innerText = "生成数独完整解...";
  setTimeout(async function() {
    Stime = new Date();
    True_Solution = setupSudokuSolution();
    LoadModalText.innerText = "生成数独谜题...";
    try {
      const tries = await fCreatePuzzle(True_Solution);
      LoadModalText.innerText = "谜题生成成功！";
      Spinner.classList.remove("spinner-border", "spinner-border-sm");
      setTimeout(() => loadingModal.hide(), 2000);
    } catch (e) {
      console.error("生成谜题时出错:", e);
      LoadModalText.innerText = "生成谜题失败，请重试";
      Spinner.classList.remove("spinner-border", "spinner-border-sm");
      setTimeout(() => loadingModal.hide(), 2000);
    }
    number_Chosen = null;
  }, 200);
}

方案2：异步调度避免栈累积（保留递归逻辑） #

通过queueMicrotask或setTimeout让每次递归调用在新的调用栈中执行，避免栈溢出。

修改后的fCreatePuzzle：

async function fCreatePuzzle(solution) {
  let refere = [];
  puzzleTries++;
  for (let i = 0; i <= 25 + difficulty - 1; i++) {
    refere[i] = getRandomLetterAndNumber(refere);
  }
  for (let i = 0; i <= refere.length - 1; i++) {
    containddd[refere[i]].Value = null;
  }
  if (!fTestSolve(solution)) {
    for (const key in containddd) {
      fChangeSudokuValAdmin(key, containddd[key].Value);
    }
    resetTest(solution);
    // 用queueMicrotask异步递归，避免栈累积
    return await queueMicrotask(() => fCreatePuzzle(solution));
  } else {
    if (puzzleTries >= 5500) {
      LoadModalText.innerText = `无法生成难度为${difficulty}的谜题`;
      console.log(`尝试${puzzleTries}次后，仍无法生成难度${difficulty}的唯一解谜题`);
      difficulty = Math.max(difficulty - 2, 0);
      console.log(`将难度降至${difficulty}重新尝试`);
      setTimeout(() => {
        LoadModalText.innerText = `降低难度至${difficulty}以避免溢出错误`;
      }, 2000);
      puzzleTries = 0;
      setTimeout(() => {
        LoadModalText.innerText = "正在加载谜题...";
      }, 1750);
      resetTest(solution);
      // 重置后继续异步递归
      return await queueMicrotask(() => fCreatePuzzle(solution));
    }
    resetTest(solution);
    // 生成成功，返回结果终止递归
    return puzzleTries;
  }
}

修改后的InitialiseGame：

function InitialiseGame() {
  loadingModal.show();
  Spinner.classList.add("spinner-border","spinner-border-sm")
  LoadModalText.innerText = "生成数独完整解..."
  setTimeout(async function(){
    Stime = new Date()
    True_Solution = setupSudokuSolution()
    LoadModalText.innerText = "生成数独谜题..."
    try {
       await fCreatePuzzle(True_Solution);
       LoadModalText.innerText = "谜题生成成功!"
       Spinner.classList.remove("spinner-border","spinner-border-sm")
       setTimeout(() => loadingModal.hide(),2000)
    } catch (e) {
      console.error("生成谜题出错:", e)
      LoadModalText.innerText = "生成谜题失败，请重试"
      Spinner.classList.remove("spinner-border","spinner-border-sm")
      setTimeout(() => loadingModal.hide(),2000)
    }
    number_Chosen = null
  },200)
}

关键改进说明 #

• 迭代模式：完全规避递归调用栈的累积，是解决栈溢出最彻底的方案。
• 异步调度：通过queueMicrotask让递归调用在新栈中执行，既保留递归逻辑又避免栈溢出。
• 终止逻辑修复：确保生成有效谜题时直接返回结果，停止循环/递归。
• 错误捕获优化：外层try/catch能正确捕获所有生成过程中的错误，包括异步操作异常。

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