关于汉诺塔的递归过程和完成所需的最少步数的问题

Question

目前，我已经学习了 3 种不同的方法来计算解决汉诺塔的最小步数。

第一种方法是：2 的“圆盘”次方减 1。总而言之，非常简单易懂。

const towerHanoi = (discs) => 2**discs - 1;

console.log(towerHanoi(0)); // 0
console.log(towerHanoi(2)); // 3
console.log(towerHanoi(3)); // 7
console.log(towerHanoi(4)); // 15 
console.log(towerHanoi(5)); // 31
console.log(towerHanoi(6)); // 63

第二种方法是使用“for 循环”。在每次迭代中，将“计数”添加到 2 的“i”次方的结果再次，非常直接和易于理解。

function towerHanoi(discs,count=0) {
  for (let i = 0; i < discs; i++) count += 2**i;
  return count;
}

然而，在递归的第三种方法中，我无法完全理解递归过程的概念。

const towerHanoi = (discs) => discs === 0 ? 0 : 2 * towerHanoi(discs-1) + 1;

让我们以5个圆盘为例来说明至少需要31步才能完成游戏的递归过程。我将尽力分解递归过程，如下所示：

2 * (5-1) + 1 === 9
2 * (4-1) + 1 === 7
2 * (3-1) + 1 === 5
2 * (2-1) + 1 === 3
2 * (1-1) + 1 === 1
9 + 7 + 5 + 3 + 1 --> 25 =/= 31

如您所见，我得到的是 25 而不是 31。我错过了什么。有人可以帮助我理解代码的递归过程吗？感谢阅读并提前万分感谢:)

Answer 1

这个递归公式背后的推理：

 const towerHanoi = (discs) => discs === 0 ? 0 : 2 * towerHanoi(discs-1) + 1;

...如下：

假设我们知道如何将 discs-1 个圆盘从一堆移到另一堆。然后我们可以按如下方式使用该知识：

将除底部以外的所有棋子移动到中间位置（使用该知识）。然后将最大的圆盘移到最后一个位置。最后将中间的堆栈移到那个最大的圆盘上，再次应用该知识。

所以确实，我们需要将一叠 discs - 1 棋子移动两次，然后再移动一次。这给了我们公式的递归部分。

至于你对5盘的分析。您没有正确应用递归。 (5-1) 不能像这样计算——它仍然需要扩展到更深的递归级别。这是应该如何完成的：

2 * (
    2 * (
        2 * (
            2 * (
                2 * (
                    0              = 0 (base case)
                ) + 1              = 1
            ) + 1                  = 3
        ) + 1                      = 7
    ) + 1                          = 15
) + 1                              = 31

关于汉诺塔的递归过程和完成所需的最少步数的问题

Question regarding the recursive process of Tower of Hanoi and the minimum amount of moves require for completion

javascript

algorithm

recursion

ecmascript-6