Home » Data Structure

Tail Recursion and Tower of Hanoi using C

Learn: In this article we are going to study about the tail recursion and we are going to deal with the famous problem of tail recursion TOWER OF HANOI. Submitted by Amit Shukla, on September 29, 2017

If the last executed statement of a function is a recursive call to itself, then this call can be eliminated by changing the value of calling parameters to those specified in the recursive call, and repeating the whole function.

The process of this transformation is shown below in figure. Figure (a) shows the storage area used by the calling program M and several copies of the recursive function P. The arrows show the flow of control. Since each cell by P to P is its last action, there is a no need to maintain the storage areas after a call, as shown in Figure (b) and Figure (c) finally, shows these calls to P as repeated in iterative fashion on the same level.

This special case when recursive call is last executed statement of the function is especially important because it frequently occurs - It is called as tail recursion. Tail recursion means that the last executed statement is a recursive call, not necessarily that the recursive call is the last statement appearing in the function. Tail recursion may appear, for example within one clause of a switch statement or if statement where other program line appears later.

Algorithm of Tower of Hanoi

This is procedure gives the recursive solution of the Tower Of Hanoi problem for N disks.

1.	If N=1, then:
	(a)	Write: BEG -> End.
	(b)	Return.
2.	[Move N-1 Disks from peg BEG to peg AUX]
	Call TOWER (N-1, BEG, END, AUX)
3.	Write: BEG -> END.
4.	[Move N-1 disks from peg AUX to END]
	Call TOWER (N-1, AUX, BEG, END)
5.	Return.

Program of Tower of Hanoi

/* Program for solution of Tower of Hanoi*/
#include<stdio.h>

void toh( int ndisk, char source, char temp, char dest )
{
	if ( ndisk > 0 )
	{
		toh ( ndisk-1, source, dest, temp );
		printf ( "Move Disk %d  %c-->%c\n", ndisk, source,dest );
		toh( ndisk-1, temp, source, dest );
	}
}

int main()
{
	char  source= 'S',temp= 'T', dest= 'D';
	int ndisk;
	
	printf("Enter the number of disks : ");
	scanf ( "%d", &ndisk );
	
	printf ("Sequence is :\n");
	toh( ndisk, source, temp, dest );
	
	return 0;
}
/*End of toh()*/

Output

First run:

Enter the number of disks : 3
Sequence is :
Move Disk 1  S-->D
Move Disk 2  S-->T
Move Disk 1  D-->T
Move Disk 3  S-->D
Move Disk 1  T-->S
Move Disk 2  T-->D
Move Disk 1  S-->D

Second Run:

Enter the number of disks : 4
Sequence is :
Move Disk 1  S-->T
Move Disk 2  S-->D
Move Disk 1  T-->D
Move Disk 3  S-->T
Move Disk 1  D-->S
Move Disk 2  D-->T
Move Disk 1  S-->T
Move Disk 4  S-->D
Move Disk 1  T-->D
Move Disk 2  T-->S
Move Disk 1  D-->S
Move Disk 3  T-->D
Move Disk 1  S-->T
Move Disk 2  S-->D
Move Disk 1  T-->D