cfunctionrecursiontowers-of-hanoi

How to index each steps of moving disk in Tower of Hanoi (recursive approach)


Printing moving disk from source to destination in TOH( Tower of Hanoi) can easily write in C/C++.(with recursive function) But how can we print index each step ? C code-

#include<stdio.h>
void tower( int disk, int peg1, int peg2, int peg3);// function declaration
int main()
{
    int disk;
    int peg1= 1, peg2= 2, peg3= 3;//numbering 
    puts("enter disk");
    scanf("%d", &disk);//read disks
    tower(disk, peg1, peg2, peg3);//function using
    return 0;
}
void tower( int disk, int peg1, int peg2, int peg3)//function definition
{
    
    if(disk ==1)//if only 1 disk is avialable
    {
    printf("move disk from peg%d to peg%d\n",peg1,peg3);//moving disk from source to destination
    }
    else
    {
      tower(disk-1, peg1,peg3,peg2);//moving n-1 disk from peg 1 to peg2 using peg3
      printf("move disk from peg%d to peg%d\n", peg1,peg3);//move last biggest disk
      tower(disk-1,peg2,peg1,peg3);//moving n-1 disk from peg2 to peg3 using peg1
    }

It works and prints output.

But Is there any way to index(1,2,...)each step like-

  1. move disk from peg1 to peg3
  2. move disk from peg1 to peg2

Solution

  • First note that you do not need to printf something in your else branch since this is being managed by your recursive function base case.

    To print the index, the easiest solution (if we rule out global variables) would be to give your recursive function an additional pointer argument referencing an integer that is the number of lines printed. Each time you print a line, the integer referenced by this pointer is incremented by 1. This gives function tower_ptr below:

    #include <stdio.h>
    
    void tower_ptr(int * index, int disk, int src, int tmp, int dst) {    
      if(disk == 1) {
        (*index) ++;
        printf("%d. move %d -> %d\n", *index, src, dst);
      } else {
        tower_ptr(index, disk - 1, src, dst, tmp);
        tower_ptr(index, 1, src, - 1, dst);
        tower_ptr(index, disk - 1, tmp, src, dst);
      }
    }
    
    int main() {
      int index = 0;
      int disk;
      puts("enter disk");
      scanf("%d", &disk);
      tower_ptr(&index, disk, 1, 2, 3);
      return 0;
    }
    

    Another solution is to give your function an additional parameter which is the next index to print. The function returns the number of indexes printed. This gives function tower_int below:

    #include <stdio.h>
    
    int tower_int(int index, int disk, int src, int tmp, int dst) {    
      if(disk == 1) {
        printf("%d. move %d -> %d\n", index + 1, src, dst);
        return index + 1;
      } else {
        index = tower_int(index, disk - 1, src, dst, tmp);
        index = tower_int(index, 1, src, - 1, dst);
        index = tower_int(index, disk - 1, tmp, src, dst);
        return index;
      }
    }
    
    int main() {
      int index = 0;
      int disk;
      puts("enter disk");
      scanf("%d", &disk);
      tower_int(0, disk, 1, 2, 3);
      return 0;
    }