# Help in Tower of Hanoi

Hi, I’v been stuck on Tower of Hanoi for quite some time now. I have a fair bit of understanding of recursion and the way function calls itself. But here in Tower of Hanoi, I am unable to understand the flow of the algorithm.
Here’s the algorithm I’m following:

T(N, Beg, Aux, End)

`````` 1. T(N-1, Beg, End, Aux)
2. T(1, Beg, Aux, End)
3. T(N-1, Aux, End)
``````

So, according to the above algorithm, First we swap N-1 disks to an auxiliary peg, then we swap the Nth peg to the destination peg and repeat the following.
But, When I take an example Say T(3, A, B, C) where I have to move disks from A to C, here are the steps that I follow:

`````` 1. (2, A, C, B) ... T(N-1, Beg, End, Aux)
2. (1, A, B, C) ... T(1, Beg, Aux)
3. ?
``````

Consider you only know how to move one ring.

Now you are asked to move 4 rings from tower A to tower C.

Understand this notation \$<n P Q R>\$, this means I want to move n rings from P to Q using R, we are going to pass n = 4, P = A, Q = C, R = B in the function.

Now we have \$<4 A C B>\$ i.e. move 4 rings from A to C using B.

You : I want to move 4 rings from A to C.\$<4 A C B>\$ (our first function call)

Me : move 3 rings from A to B \$<3 A B C>\$ (first recursive call). then move one (yellow) ring from A to C \$<1 A C B>\$ (this is the only move you know). then move those three rings from B to C \$<3 B C A>\$ (we will make this call when we have moved 3 rings from A to B).

thus, **a <4 A C B> call is <3 A B C>,<1 A C B>,<3 B C A> executed in order.

You: I don’t know how to move 3 rings from A to B(thus we have a three ring problem <3 A B C> ).

ME: move 2 rings from A to C <2 A C B> (second recursive call). <1 A B C> then <2 C B A > thus a <3 A B C> call is <2 A C B><1 A B C><2 C B A> executed in order.

But the thing is you didn’t know how to how to move the 2 rings**<2 A C B >.**

thus, we have a 2 ring problem**.<2 A C B>**(third recursive call).

this is how <2 A C B> executes (you know all the moves in this call as you know how to move 1 ring):-

<2 A C B> call is <1 A B C> <1 A C B > <1 B C A> executed in order

<1 A B C> return; <1 A C B >return; <1 B C A>return; this completes the <2 A C B> call, hence it also returns to the calling function

<3 A B C >;

next is <1 A B C> return; next call is made to <2 C B A> all the subsequent move are the base condition recursive calls

<1 C A B>return; <1 C B A> return; <1 A B C> return; This concludes the <3 A B C> call and it returns;

Next call is <1 A C B> return; Next call is <3 B C A>

you must have an idea now how it would be done.

<3 B C A> is <2 B A C><1 B C A><2 A C B>

now we will execute <2 B A C>

<2 B A C> is <1 B C A><1 B A C ><1 C A B>executed in order.

<1 B C A>return; <1 B A C >return; <1 C A B>return; this concludes the <2 B A C> part of <3 B C A>. i.e. <2 B A C>returns;

next call is:-

<1 B C A>return; next call is <2 A C B>

<2 A C B> is <1 A B C><1 A C B><1 B C A> executed in order.

<1 A B C>return; <1 A C B>return; <1 B C A>return; <2 A C B> returns; <3 B C A> returns;

<4 A C B >returns;

You: I want to move n rings from A to C.

Me: **\$<n-1 A B C>

<\$1 A C B\$>

<n-1 B C A>\$…**.

Source : Quora

2 Likes

Hey @codex0196 thanks for such detailed answer… But can you help me with the order of execution here… See the first step is < n-1, A, B, C > i.e move n-1 disks from A to B so when the execution reaches this point so function call would be returning to this function itself right? i.e after < n-1, A, B, C > the next call should be <n-2, A,B,C> until n==1 right?