Unit 6: Recursion
Recursion:
Recursion is the concept of repeating the execution of statements by calling the procedure or
function itself until some specified condition is satisfied.
A procedure or a function is called as recursive if it has following properties:
i. It should call itself.
ii. It should have a stopping condition (also called as base criteria).
iii. Each time the procedure calls itself, it should be closer to the stopping condition.
Recursion helps for repeating the execution of statements multiple time similar to loop.
However, it is not as efficient as loop in terms of processing speed and memory utilization.
Differentiate between recursion and iteration (loop)
Recursion Iteration (loop)
1) Recursion is the concept of repeating 1) Iteration is the concept of repeating
the execution of statements for the execution of statements for
multiple times by calling the multiple times until some specified
procedure or function itself, until condition is satisfied.
some specified condition is satisfied.
2) It requires longer processing time than 2) It requires smaller processing time
iteration. than recursion.
3) It is slower. 3) It is faster.
4) It has larger memory requirement. 4) It has smaller memory requirement.
5) It is not as efficient as iteration, so it is 5) It is more efficient than recursion, so it
rarely used. is commonly used.
6) It reduces the size of the program 6) It makes the program code lengthy as
code. compared to recursion.
7) It contains a stopping condition and 7) It contains initialization, condition,
function call to call itself. update and the statement to execute.
8) It uses STACK to store values during 8) It doesn’t use STACK.
execution.
9) It is the most natural way to solve 9) It is complex to solve those problems
some problems like calculating using iteration. However, for others it
factorial, Fibonacci, solving TOH is the most efficient technique.
(Tower of Hanoi).
10) Example: 10) Example:
fact (n) for(i=n;i>=1;i--)
{ {
if n=1 fact=fact*i
return (1); }
else
return (n*fact(n-1))
}
Applications of Recursion:
1. Factorial calculation
2. Fibonacci sequence generation
3. TOH (Tower of Hanoi)
4. Binary Search
5. BST (Binary Search Tree)
6. Merge Sort
7. Quick Sort
Advantages of Recursion:
1. It is the most natural way to solve some problems like factorial, Fibonacci, TOH (Tower of
Hanoi).
2. It reduces the size of program code.
Disadvantages of Recursion:
1. It requires longer processing time.
2. It has larger memory requirement.
3. It is not as efficient as iteration.
4. It is slower.
Types of recursion:
1. Direct recursion
2. Indirect recursion
Direct recursion Indirect recursion
Function () Function 1()
{ {
Function 2()
Function (); }
} Function 2()
{
Function 1()
}
In direct recursion, the function call itself In indirect recursion, the function call another
directly. function which again calls the initial function.
Algorithm to calculate factorial of a number:
1. START
2. Input a number (n)
3. Factorial (n)
{
If n=0 OR n=1
return (1)
else
return (n*Factorial (n-1))
}
4. EXIT
Working Steps
n=5
5*Factorial (4)
5*4*Factorial (3)
5*4*3*Factorial (2)
5*4*3*2*Factorial (1)
5*4*3*2*1
5*4*3*2
5*4*6
5*24
120
Algorithm to calculate the term of Fibonacci series
[Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, 21 …………]
1. START
2. Input the value of n (term)
3. Fibo (n)
{
If n=1
Return (0)
Else n=2
Return (1)
Else
Return (Fibo (n-1) + Fibo (n-2))
}
4. EXIT
Tower of Hanoi (TOH)
TOH is one of the classical problem that can be solved by using recursion.
It is a game that contains three pegs/stands (BEG, AUX, END). BEG contains n number of discs with
decreasing size on bottom to top. The target/goal of the game is to move all the disk from BEG to END
using AUX. The rule of the game are:
i) Only one disc can be moved at a time. Only the top disc of any peg can be moved to any other
peg.
ii) A larger disc cannot be placed above the smaller one at any point of time.
Example with n=3
Here, A=BEG, B=AUX, C=END
1) BEG→END 5) AUX→BEG
2) BEG→AUX 6) AUX→END
3) END→AUX 7) BEG→END
4) BEG→END
Number of steps=2n-1
n=3, 23-1=7
n=4, 24-1=15
Task: 4-disk TOH
Logic to solve TOH:
1) Move N-1 disks from BEG to AUX recursively.
2) Move disk from BEG to END.
3) Move N-1 disks from AUX to END recursively.
Algorithm to solve TOH
1. START
2. Input the number of disk (N)
3. TOH (N, BEG, AUX, END)
a) If n=1, then:
i) Write: BEG→END
ii) Return
b) [Move N-1 disk from BEG to AUX using END]
Call TOH (N-1, BEG, END, AUX)
c) Write: BEG→END
d) [Move N-1 from AUX to END using BEG]
Call TOH (N-1, AUX, BEG, END)
e) Return