Question regarding the recursive process of Tower of Hanoi and the minimum amount of moves require f-CodePudding

Currently, I've learned 3 different approaches to count the minimum amount of moves to solve the Tower of Hanoi.

The first approach is: 2 to the power of "discs" minus 1. All in all, very straight forward and comprehensible.

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

The second approach is with a "for loop." On each iteration, add "count" to the result of 2 to the power of "i" Once again, very straight forward and comprehensible.

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

In the third approach with recursion, however, I just couldn't quite grasp the concept the recursive process.

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

Let's use 5 discs as our example to illustrate the recursive process which requires a minimum of 31 moves to complete the game. I'm going to try my best to break down the recursive process as I can as followed:

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

As you can see, I get 25 instead of 31. What am I missing. Can someone kindly help me understand the recursive process of the code? Thanks for reading and million thanks in advance :)

CodePudding user response：

The reasoning behind this recursive formula:

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

...is as follows:

Let's assume we know how to move discs-1 discs from one pile to another. Then we can use that knowledge as follows:

Move all discs, excepts the bottom one, to the middle spot (using that knowledge). Then move the greatest disc to the final spot. Finally move the middle stack on top of that greatest disc, again apply that knowledge.

So indeed, we need to move twice a stack of discs - 1 discs, and make one other move. That gives us that recursive part of the formula.

As to your analysis for 5 discs. You didn't apply the recursion correctly. The (5-1) cannot be evaluated just like that -- it still needs to be expanded into deeper recursion levels. Here is how it should be done:

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