CODEWITHSUNDEEP
crecursiontowers-of-hanoi
AL-zami
AL-zami

Reputation: 9066

Need an explanation of the recursive calls in "Towers of Hanoi"

I understand the concept of recursion and how it stacks up with each call. But I fail to explain how recursive calls are working and gets printed when there are two function call separated by a printf command. Can anyone explain to me how this recursive call is working?

I have found an example regarding a game called "Towers of Hanoi". Ut was used as an example of recursion. The code:

#include <stdio.h>

void transfer(int n, char from, char to, char temp);

int main()
{
    int n;

    printf("how many disk");
    scanf("%d", &n);
    printf("\n");
    transfer(n, 'L', 'R', 'C');
    return 0;
}

/*
 * n = number of disk,
 * from = origin,
 * to = destination,
 * temp = temporary storage
 */
void transfer(int n, char from, char to, char temp)
{
    if (n > 0) {
        // Move n-1 disks from origin to temporary
        transfer(n - 1, from, temp, to);

        // Move n th disk from origin to destination
        printf("move disk %d from %c to %c\n", n, from, to);

        // Move n-1 disks from temporary to destination
        transfer(n - 1, temp, to, from);
    }
}

for n=3 it gives output like this

move disk 1 from L to R //
move disk 2 from L to C // 
move disk 1 from R to C // 
move disk 3 from L to R // 
move disk 1 form C to L // 
move disk 2 from C to R //
move disk 1 from L to R //

Upvotes: 0

Views: 1547

Answers (2)

phoxis
phoxis

Reputation: 61910

I wrote this post to answer exactly such a question, which I believe a significant number of beginners face.

What happens is When you have n disks.

Task is move n disks from L to R through T , which can be broken down to:

  1. Move the top n-1 disks from L to T
  2. Move the bottom disk from L to R
  3. Move the n-1 disks from T to R

Now note that the step 1 and 3 are itself a Towers of Hanoi problem with n-1 disks and different source and destination poles. The step 1 is a problem to move n-1 disks from L to T through R and step 2 is a problem to move n-1 disks from T to R through L.

Thus the problem is broken down to sub-problems which can be solved in one step, which is a 2 disk problem instance.

  1. Move top disk from L to T
  2. Move bottom disk from L to R
  3. Move top disk from T to R

Upvotes: 1

NorbertM
NorbertM

Reputation: 1326

You might be thinking of recursion in a special variant called "end-recursive" !? The tower of hanoi algorithm is NOT end-recursive. Instead it uses recursion even twice:

  1. Move N-1 disks above disk N to temporary stack (1st transfer() function call)
  2. move disk N to destination stack (printf)
  3. Move back the N-1 disks from temporary stack to destination bove disk N (2nd transfer() function call)

The idea behind the transfer() function recursion is: If it is called with n>1 disks to operate on, it delegates 'work' to recursive invocations of itself. If called with n==1 it just moves the disk.

Here is a modified version which should make things clearer:

void transfer(int n, char from, char to, char temp)
{
    if (n > 1) {
        // Move n-1 disks from origin to temporary
        transfer(n - 1, from, temp, to);
    }

    // Move n th disk from origin to destination
    printf("move disk %d from %c to %c\n", n, from, to);

    if (n > 1) {
        // Move n-1 disks from temporary to destination
        transfer(n - 1, temp, to, from);
    }
}

Upvotes: 0

Related Questions