CODEWITHSUNDEEP
recursiontowers-of-hanoi
sad
sad

Reputation: 820

Recursion in Towers of hanoi

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.

Upvotes: 0

Views: 287

Answers (2)

Mike Seymour
Mike Seymour

Reputation: 254631

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)

Upvotes: 0

valjeanval42
valjeanval42

Reputation: 132

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.

Upvotes: 0

Related Questions