Hanoi Towers recursive expression for EVERY algorithm

Question

What the recursive algorithm for moving $n$ disks says, is:

1. If $n > 1$, move $n-1$ discs from A to B.
2. Move the $n$th disk from A to C.
3. If $n > 1$, move $n-1$ discs from B to C.

Let $T_n$ be the number of moves for moving n disks.

We have $ T_n=2T_{n-1}+1 , T_1=1 $, so $T_n=2^n-1, n \geq 1 $

Is it correct to say that for every algorithm solving the Hanoi Towers problem, it is true that $$ T_n=2T_{n-1}+c $$ So, we would need to know $c$ (number of moves for moving the last disk from A to C) and some other $T_i$, in order to calculate $T_ n$ for every $n$.

Thank you in advance

Answer 1

"Every algorithm" is quite a large set of algorithms. If you draw, even for three disks, the graph of possible states and the moves between them, you get a very complicated picture:

Here, I'm representing a state as a string of the location of the first, second, and third disk, so we are trying to get from aaa to ccc.

An algorithm would just be any method of doing that. If you wanted the algorithm to be memoryless, in the sense that it always does the same thing from any state, then you could get the number of moves to $T_n = 3^n-1$, by taking the most indirect route possible, and visiting every single other state before we get from aa...a to cc...c. If not, then you could make the algorithm take arbitrarily long, for example by following the rule "Move the first disk around $2^{2^n}$ times, then use the ordinary algorithm."

In particular, it's not true that every algorithm obeys a recurrence of the form $T_n = 2T_{n-1} + c$. A general algorithm:

• Doesn't need to move the last disk from A to C directly, but could move the last disk from A to B to C (going around the diagram above the long way).
• Doesn't need to take a constant number of steps, $c$, to move the last disk from A to C, but could take a number of steps depending on $n$.
• Doesn't need to follow similar rules before the last disk is moved, and after it is moved. (The fact that the standard algorithm does follow the same rule in both cases is what gives us the $2T_{n-1}$ term.)