# 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions