Data Structures and Algorithms - Old Questions
2. Why recursion is required? Explain with Tower-of-Hanoi example. How recursive algorithm makes program effective? Write the merits and demerits of recursion in Programming.
Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result.
Recursion is required because there are problems to solve which are recursive by nature. Non-recursive solutions to those problems are
- Complicated (because of the mismatch between the problem and the code) Fragile (be
- cause complicated)
- Harder to maintain and analyse (because of points 1 and 2)
- Potentially less efficient
Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.
In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.
Algorithm for TOH problem:
Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.
1. Assign three pegs A, B & C
2. If n==1
Move the single disk from A to C and stop.
3. If n>1
a) Move the top (n-1) disks from A to B.
b) Move the remaining disks from A to C
c) Move the (n-1) disks from B to C
4. Terminate
Example for 3 disks: 7 moves
Merits of recursion
1. The code may be easier to write.
2. To solve such problems which are naturally recursive such as tower of Hanoi.
3. Reduce unnecessary calling of function.
4. Extremely useful when applying the same solution.
5. Recursion reduce the length of code.
6. It is very useful in solving the data structure problem.
7. Stacks evolutions and infix, prefix, postfix evaluations etc.
Demerits of recursion
1. Recursive functions are generally slower than non-recursive function.
2. It may require a lot of memory space to hold intermediate results on the system stacks.
3. Hard to analyze or understand the code.
4. It is not more efficient in terms of space and time complexity.
5. The computer may run out of memory if the recursive calls are not properly checked.