JavaScript汉诺塔算法的非递归迭代实现方案

作者:沉舟时间:2026-11-22 10:28:19浏览:525

深入解析JavaScript中汉诺塔问题的非递归迭代实现方案,涵盖基于循环规律的数学迭代法与基于显式栈调用的状态机模拟,助你规避调用栈溢出并实现单步可视化。

分类:算法工程与JavaScript进阶 类型:非递归迭代 / 状态机设计
JavaScript汉诺塔算法的非递归迭代实现方案

汉诺塔(Tower of Hanoi)是计算机科学中展示递归思想的经典范例,但将递归改写为非递归迭代并不只是为了完成一道算法作业。在 JavaScript 运行环境中,默认调用栈深度通常仅在 10000 左右,且在现代前端动画、单步调试器或可中断交互界面的开发中,递归调用具有“不可暂停、一口气执行到底”的天然局限。本文将直接呈现两种能够工业化落地的 JavaScript 汉诺塔非递归迭代方案:基于奇偶循环位移律的数学迭代法与基于显式调用栈的状态机模拟法,并给出可直接运行的完整代码及应用要点。

一、汉诺塔的本质约束与递归的瓶颈

汉诺塔问题规定有三根柱子(起始柱 A、辅助柱 B、目标柱 C)以及 n 个尺寸互不相同的圆盘。游戏必须严格遵守两条核心物理规则:每次只能搬动任意柱子顶端的一枚圆盘;在整个搬移过程中,任何较大尺寸的圆盘都绝对不能压在较小尺寸圆盘之上。

用经典递归表达这一过程仅需 3 行核心代码:先将上方的 n - 1 个盘移到辅助柱,再把最大的第 n 号盘移到目标柱,最后将 n - 1 个盘从辅助柱移到目标柱。然而在实际工程应用中,递归实现会暴露明显的痛点:

  • 调用栈深度的物理天花板:当规模扩大或在资源受限的嵌入式 JS 引擎中运行时,深层嵌套很容易触发 RangeError: Maximum call stack size exceeded。
  • 过程控制力缺失:浏览器的单线程事件循环无法在纯递归执行途中轻松交出控制权。若要在页面上实现“点击按钮单步执行一步”或带有缓动动画的演示,递归函数很难优雅地在任意步暂停并持久化当前柱子状态。
JavaScript汉诺塔算法的非递归迭代实现方案
图 1:汉诺塔状态与移动合法性原理(两根非1号盘柱子间的移动具备绝对唯一性)

二、方案一:基于循环移动律的非递归迭代法

数学家们在分析汉诺塔的二进制特征时发现了一个极为优美的确定性规律:总搬运步数恒为 2^n - 1 步。在这漫长的搬运序列中,圆盘的移动遵循着严格的交替节奏。

1. 规律推导与移动公理

这一迭代方案完全不需要任何递归,其核心由两个确凿无歧义的规则构成:

  1. 奇数步(第 1, 3, 5, 7... 步):永远移动最小的 1 号圆盘。它的移动方向完全由盘子总数 n 的奇偶性决定,且在三根柱子之间单向循环:
    • 若 n 为偶数,1 号盘的移动环路为:A → B → C → A;
    • 若 n 为奇数,1 号盘的移动环路为:A → C → B → A。
  2. 偶数步(第 2, 4, 6, 8... 步):必定移动非 1 号盘。此时观察不包含 1 号盘的另外两根柱子,由于大盘不可压小盘的刚性约束,这两根柱子顶端之间有且仅有一种合法的移动方式(较小的顶部盘移动到较大的顶部盘上,或者将顶部盘移入空柱)。
JavaScript汉诺塔算法的非递归迭代实现方案
图 2:循环规律推演与奇偶步迭代执行流程

2. 方案一 JavaScript 完整实现

我们在 JavaScript 中使用三个数组充当柱子的容器,使用数组尾部模拟柱子顶端。整个求解过程由一个标准的 for 循环驱动,彻底杜绝函数重入:

/**
 * 基于循环规律的汉诺塔非递归迭代求解
 * @param {number} n 圆盘总数
 * @param {string} from 起始柱标识
 * @param {string} to 目标柱标识
 * @param {string} aux 辅助柱标识
 * @returns {Array<{step: number, disk: number, from: string, to: string}>}
 */
function hanoiIterativeByPattern(n, from = 'A', to = 'C', aux = 'B') {
  if (n <= 0) return [];

  // 使用数组模拟柱子栈,柱底在下标0,柱顶在末尾
  const pegs = {
    [from]: Array.from({ length: n }, (_, i) => n - i), // 例如 [3, 2, 1]
    [to]: [],
    [aux]: []
  };

  // 确定 1 号盘在三根柱子间的流转环路
  const cycle = n % 2 === 0 ? [from, aux, to] : [from, to, aux];
  let disk1Peg = from; // 记录 1 号盘当前所在柱

  const totalSteps = Math.pow(2, n) - 1;
  const moveHistory = [];

  for (let step = 1; step <= totalSteps; step++) {
    if (step % 2 === 1) {
      // 【奇数步】:移动 1 号圆盘
      const currentIdx = cycle.indexOf(disk1Peg);
      const nextPeg = cycle[(currentIdx + 1) % 3];

      const disk = pegs[disk1Peg].pop();
      pegs[nextPeg].push(disk);

      moveHistory.push({ step, disk, from: disk1Peg, to: nextPeg });
      disk1Peg = nextPeg;
    } else {
      // 【偶数步】:在另外两根柱子之间做唯一合法移动
      const otherPegs = Object.keys(pegs).filter(p => p !== disk1Peg);
      const [pegX, pegY] = otherPegs;
      
      const topX = pegs[pegX].length > 0 ? pegs[pegX][pegs[pegX].length - 1] : Infinity;
      const topY = pegs[pegY].length > 0 ? pegs[pegY][pegs[pegY].length - 1] : Infinity;

      let moveFrom, moveTo;
      if (topX < topY) {
        moveFrom = pegX;
        moveTo = pegY;
      } else {
        moveFrom = pegY;
        moveTo = pegX;
      }

      const disk = pegs[moveFrom].pop();
      pegs[moveTo].push(disk);

      moveHistory.push({ step, disk, from: moveFrom, to: moveTo });
    }
  }

  return moveHistory;
}

// 执行示例 (n = 3)
const stepsFor3Disks = hanoiIterativeByPattern(3, 'A', 'C', 'B');
stepsFor3Disks.forEach(item => {
  console.log(`第 ${item.step} 步: 移动圆盘 ${item.disk} 从柱 ${item.from} 到柱 ${item.to}`);
});
示例输出结果 (n = 3):
第 1 步: 移动圆盘 1 从柱 A 到柱 C
第 2 步: 移动圆盘 2 从柱 A 到柱 B
第 3 步: 移动圆盘 1 从柱 C 到柱 B
第 4 步: 移动圆盘 3 从柱 A 到柱 C
第 5 步: 移动圆盘 1 从柱 B 到柱 A
第 6 步: 移动圆盘 2 从柱 B 到柱 C
第 7 步: 移动圆盘 1 从柱 A 到柱 C

三、方案二:基于显式调用栈的状态机模拟法

数学规律迭代固然高效,但需要事先了解汉诺塔特有的奇偶环路。在更具通用性的算法重构场景中,将任意递归转化为非递归的标准模式是在堆内存中维护一个模拟栈(Simulated Call Stack)。

1. 栈帧与状态拆解机制

在 JavaScript 引擎执行递归时,每个调用上下文都保留了局部变量和当前的执行位置。我们可以在堆中构造一个 Frame 对象:{ n, from, to, aux, stage }。

  • stage 0:对应递归第一段,相当于准备执行 hanoi(n - 1, from, aux, to)。我们将当前帧的状态更新为 stage = 1,并将新的子任务帧压入栈顶。
  • stage 1:对应中间的核心搬移动作,记录圆盘 n 从 from 移动到 to;随后将当前帧更新为 stage = 2,并将第二段子任务 hanoi(n - 1, aux, to, from) 压入栈顶。
  • stage 2:两个子任务及自身搬移全部完成,执行 stack.pop() 销毁此帧。
JavaScript汉诺塔算法的非递归迭代实现方案
图 3:显式栈模拟递归与帧状态转移图

2. 方案二 JavaScript 完整实现

/**
 * 基于显式调用栈状态机模拟的非递归汉诺塔
 * @param {number} totalDisks 
 * @param {string} from 
 * @param {string} to 
 * @param {string} aux 
 */
function hanoiIterativeByStack(totalDisks, from = 'A', to = 'C', aux = 'B') {
  if (totalDisks <= 0) return [];

  const moves = [];
  let stepCounter = 0;

  // 显式模拟调用栈
  const stack = [
    { n: totalDisks, from, to, aux, stage: 0 }
  ];

  while (stack.length > 0) {
    const top = stack[stack.length - 1];

    // 基本边界条件:若盘数为 1,直接移动并弹出
    if (top.n === 1) {
      stepCounter++;
      moves.push({ step: stepCounter, disk: 1, from: top.from, to: top.to });
      stack.pop();
      continue;
    }

    if (top.stage === 0) {
      // 阶段 0:将状态推入阶段 1,并优先执行前置子递归任务
      top.stage = 1;
      stack.push({
        n: top.n - 1,
        from: top.from,
        to: top.aux,
        aux: top.to,
        stage: 0
      });
    } else if (top.stage === 1) {
      // 阶段 1:此时前半段 n-1 盘已经挪开,搬动第 n 号盘
      stepCounter++;
      moves.push({ step: stepCounter, disk: top.n, from: top.from, to: top.to });

      // 推进到阶段 2,并将后半段子递归任务压栈
      top.stage = 2;
      stack.push({
        n: top.n - 1,
        from: top.aux,
        to: top.to,
        aux: top.from,
        stage: 0
      });
    } else {
      // 阶段 2:后半段已完成,当前帧生命周期完结
      stack.pop();
    }
  }

  return moves;
}
深度与内存开销分析:

虽然模拟栈也是栈,但它分配在 JavaScript 的 V8 堆内存中,其最大容纳帧数受限于几百兆甚至数吉字节的堆空间,而非执行环境分配给执行栈的区区几兆字节。更关键的是,模拟栈的最大深度其实严格受限于 n(即 $O(n)$ 空间),这保证了该方案在大规模盘数下绝不会触发运行环境的崩溃异常。

四、工程实战:结合 Generator 构造单步动画迭代器

在前端交互场景(例如为用户展示汉诺塔搬运的动态 Canvas 或 DOM 动画)中,最理想的模型并非一次性计算出数万条历史步骤并塞进内存数组,而是让算法成为一个随用随取、可随时挂起与恢复的迭代器。利用 ES6 的 function* 生成器配合显式状态迭代,可以实现优雅的单步控制:

/**
 * 生成器版本的非递归汉诺塔单步驱动器
 */
function* createHanoiStepper(n, from = 'A', to = 'C', aux = 'B') {
  const stack = [{ n, from, to, aux, stage: 0 }];
  let step = 0;

  while (stack.length > 0) {
    const top = stack[stack.length - 1];

    if (top.n === 1) {
      step++;
      yield { step, disk: 1, from: top.from, to: top.to };
      stack.pop();
      continue;
    }

    if (top.stage === 0) {
      top.stage = 1;
      stack.push({ n: top.n - 1, from: top.from, to: top.aux, aux: top.to, stage: 0 });
    } else if (top.stage === 1) {
      step++;
      yield { step, disk: top.n, from: top.from, to: top.to };
      top.stage = 2;
      stack.push({ n: top.n - 1, from: top.aux, to: top.to, aux: top.from, stage: 0 });
    } else {
      stack.pop();
    }
  }
}

// 使用方式:在 UI 交互中按需触发单步
const stepper = createHanoiStepper(3);
// 每次点击「下一步」按钮调用 stepper.next():
console.log(stepper.next().value); // { step: 1, disk: 1, from: 'A', to: 'C' }
console.log(stepper.next().value); // { step: 2, disk: 2, from: 'A', to: 'B' }

五、两种迭代方案与递归的选型对比

在面对不同的业务需求时,选择哪种实现取决于你的首要目标:是代码简洁性、极限计算吞吐,还是对交互过程的可控粒度。

JavaScript汉诺塔算法的非递归迭代实现方案
图 4:汉诺塔主流算法实现维度全面对比与选型总结

工程落地中的避坑指南

  • 大数步数安全范围:由于步数为 2^n - 1,当 n > 53 时,总步数将超过 JavaScript 中 Number.MAX_SAFE_INTEGER(即 9007199254740991)。此时若进行总步数遍历或计数,需改用 BigInt(例如 (1n << BigInt(n)) - 1n),以避免浮点数精度截断导致死循环。
  • 内存驻留问题:如果圆盘总数较大(如 n = 25,移动步数超 3300 万次),一次性将所有移动历史存储在 moveHistory 数组中会导致几个吉字节的内存消耗。此时务必采用生成器(Generator)按流式消费,或在每一步通过回调函数直接处理并释放。
  • 不可变状态持久化:在构建图形界面快照或撤销(Undo/Redo)功能时,切忌直接向每根柱子数组内做原位引用共享。应深拷贝柱子对象,确保前后状态互不污染。
作者最新文章
相关文章
更多