如何用非递归方式实现汉诺塔？求JavaScript解决方案（附报错代码）

原代码问题分析 #

你的代码存在两处核心错误：

• 数组引用问题：const tmp = path 是赋值引用而非拷贝，导致后续循环中修改path的同时，tmp的长度也会动态变化，最终错误地重复添加大量无效移动步骤。
• 柱子编号计算逻辑错误：nextPile = 1 + ((n + 1) % 2) 无法正确对应汉诺塔的移动规则，导致生成的路径完全不符合从a到c的目标要求。

正确的非递归实现（栈模拟法） #

非递归实现汉诺塔最直观的方式是用栈模拟递归调用栈，保存每一步需要处理的状态（盘子数量、起始柱、辅助柱、目标柱）：

const hanoi = (n) => {
  const sign = ['a', 'b', 'c'];
  // 栈元素结构：[待移动盘子数, 起始柱索引, 辅助柱索引, 目标柱索引]
  const stack = [[n, 0, 1, 2]];

  while (stack.length > 0) {
    const [count, from, aux, to] = stack.pop();
    if (count === 1) {
      // 单个盘子直接移动
      console.log(`${sign[from]} -> ${sign[to]}`);
      continue;
    }
    // 按递归逻辑逆序压栈（栈后进先出，需保证执行顺序正确）
    // 1. 把n-1个盘子从辅助柱移到目标柱，起始柱当辅助
    stack.push([count - 1, aux, from, to]);
    // 2. 把第n个盘子从起始柱移到目标柱
    stack.push([1, from, aux, to]);
    // 3. 把n-1个盘子从起始柱移到辅助柱，目标柱当辅助
    stack.push([count - 1, from, to, aux]);
  }
};

// 测试：3个盘子，从a到c
hanoi(3);

代码说明 #

• 栈用来保存递归过程中的子问题，每次弹出一个状态处理：
  • 若只有1个盘子，直接输出移动路径；
  • 若有多个盘子，将递归的三个步骤逆序压入栈（因为栈是后进先出，确保执行顺序和递归一致）：
    1. 移动n-1个盘子到辅助柱；
    2. 移动第n个盘子到目标柱；
    3. 移动n-1个盘子从辅助柱到目标柱。

运行hanoi(3)会输出正确的移动步骤：

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

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