Help in Tower of Hanoi

[montycs]

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. ?

I am really confused as which step(s) will follow afterwards. Please help me in figuring out this algorithm. Also, if possible please help me in understanding which functions would go in the stack sequentially…

[codex0196]

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

[montycs]

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?

[montycs]

@codex0196 please check my answer

[codex0196]

@montycs Figure it out by yourself because it is just a basic thing. If you can figure it out an aptitude will be built and it will help you in future.

[codex0196]

@montycs Sorry for the late reply, I was busy in my exams so thats why i was not able to answer.