Recursion in Towers of hanoi

Question

I have read the Towers of Hanoi problem statement and the solution as well. The solution states that when you have to move a set of N disks from A to B, use C as temp and transfer N-1 disks from A to C. Then transfer Nth disk from A to B and then transfer the N-1 disks from C to B. I know that the problem has reduced in size and therefore a contender for implementation recursively. However, we cannot transfer more than 1 disk at a time. How can we transfer N-1 disks in the first place.

See http://stackoverflow.com/q/25625964/489590 for more details. — Brian Cain, Sep 02 '14 at 14:36
Transfer `N-1` disks the same way you transferred `N` disks, recursively. When you get down to one disk, the transfer is trivial. — Paul, Sep 02 '14 at 14:37
@Srinath Kattula: If you tag this question with C++ add some source code please or remove the tag. — Leo Chapiro, Sep 02 '14 at 14:37
@BrianCain Lol! @Srinath Kattula, we can perform `N-1` transfers, by performing transfer of one disk `N-1` times. If it's what you are asking. Hope it isn't. — Ivan Aksamentov - Drop, Sep 02 '14 at 14:39
@Srinath I advise you to study first how recursion works using a simpler example, for instance the fibonacci sequence. Once you can manage recursion well, turn back to this problem. — nbro, Sep 02 '14 at 14:41
Hi . Thanks all. @usar, I did it just that I wanted to confirm. — sad, Sep 02 '14 at 16:05

score 0 · Answer 1 · edited May 23 '17 at 12:12

By using the recursion. See also Tower of Hanoi: Recursive Algorithm and the wikipedia page

The recursion is as follow: You know how to move 1 disc, suppose you know how to move n-1 discs, how do you move n discs?

The "suppose" part is your recursion: You move 10 discs by moving 9, then 1 then 9.
To move the 9 discs, you move 8, then 1, then 8.
To move the 8 discs...
...
To move the 2 discs, you move 1, then 1, then 1.

score 0 · Answer 2 · answered Sep 02 '14 at 14:41

That's the recursive step. Transfer N-1 disks from A to C using the same algorithm that transfers N disks from A to B. If N is one, then simply move the single disk. (Or, equivalnently, if N is zero, do nothing).

In pseudocode:

move(N, A, B):
    if (N > 0)
        move(N-1, A, C)
        move_single_disk(A, B)
        move(N-1, C, B)

Recursion in Towers of hanoi

2 Answers2