Tower Of Hanoi and  Fibonacci sequence

Tower of Hanoi 

The Tower of Hanoi problem is a classic problem in computer science and mathematics that can be elegantly solved using recursion. It involves three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, with the smallest disk at the top, thus forming a conical shape. The objective is to move the entire stack to another rod, while obeying the following rules:

• Only one disk can be moved at a time.
• Each move consists of taking the top disk from one stack and placing it on top of another stack.
• No disk may be placed on top of a smaller disk.

The initial and final state of TOH is shown in figure below:

The problem can be easily solved recursively with the following steps:

Base Case: If there is only one disk to move, simply move it to the destination rod.

Recursive Case: If there are more than one disk, follow these steps:

• Move the top n-1 disks from the source rod to an auxiliary rod using the destination rod as the intermediary.
• Move the largest disk from the source rod to the destination rod directly.
• Move the n-1 disks from the auxiliary rod to the destination rod using the source rod as the intermediary.

This process is repeated recursively for each smaller stack of disks until the base case is reached, effectively solving the Tower of Hanoi puzzle.

Algorithm to solve Tower of Hanoi puzzle recursively:

Algorithm: Tower of Hanoi

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

C program to implement Tower of Hanoi

#include<stdio.h>
void toh(int disk,char src,char aux,char dest){
   if(disk==1){
       printf("\n move %d from %c to %c\n",disk,src,dest);
   }
   else{
       toh(disk-1,src,dest,aux);
       printf("\n move %d from %c to %c\n",disk,src,dest);
       toh(disk-1,aux,src,dest);
   }
}
int main(){
   char src='A',dest='C',aux='B';
   int num;
   printf("Enter a number of disks: ");
   scanf("%d",&num);
   toh(num,src,aux,dest);
   return 0;
}

Tree recursion[Fibonacci Sequence]

In a recursive function, if there is another recursive call in the set of operations to be completed after the recursion is over, this is called a tree recursion. Examples of tree recursive functions are the quick sort and merge sort algorithms, the FibSeries algorithm, and so on.

The Fibonacci function FibSeries() is defined as:

fibonacci(0)=0

fibonacci(1) = 1 

fibonacci(2) = fibonacci(0) + fibonacci(1)

fibonacci(3) = fibonacci(1) + fibonacci(2)

fibonacci(4) = fibonacci(2) + fibonacci(3)

The above recursive call can be generalized as:

fibonacci(n) = n                            if(n==0 || n==1) 

else

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

The above generalization can be expressed as tree recursion as follows:

C code to implement fibonacci series

#include<stdio.h>
int fib(int num){
   if(num==0 || num==1) return num;
   else return fib(num-1)+fib(num-2);
}
int main(){
   int num,i;
   printf("Enter a number: ");
   scanf("%d",&num);
   for(int i=0;i<=num;i++)
   {
       printf("%d\t",fib(i));
   }
   printf("\n");
   return 0;
}