BIM SEM - III
Data Structures & Algorithms
Unit 5: Recursion
Syllabus:
=================================================================
Introduction:
Some computer programming languages allow a module or function to calls itself. This
technique is known as recursion. In recursion, a function (a) either calls itself directly or calls
a function (b) that in turn calls the original function (a). The function (a) is called recursive
function.
Syntax of direct recursion
int fun()
{
// some codes
fun();
}
Syntax of indirect recursion
int fun()
{
// some codes
fun2();
}
int fun2()
{
// some codes
fun();
}
Properties of recursion function
A recursive function can go infinite like a loop. To avoid infinite running of recursive
function, there are two properties that a recursive function must have
Base criteria: There must be at least one base criteria or condition, such that, when
this condition is met the function stops calling itself recursively.
Progressive approach: The recursive calls should progress in such a way that each
time a recursive call is made it comes closer to the base criteria.
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Principle of recursion:
The recursion is a process by which a function calls itself. We use recursion to solve
bigger problem into smaller sub-problems. One thing we have to keep in mind, that if each
sub-problem is following same kind of patterns, then only we can use the recursive approach.
A recursive function has two different parts, one is base case and another is recursive case.
The base case is used to terminate the task of recurring. If base case is not defined, then the
function will recur infinite number of times.
In computer program, when we call one function, the value of the program counter is stored
into the internal stack before jumping into the function area. After completing the task, it
pops out the address and assign it into the program counter, then resume the task. During
recursive call, it will store the address multiple times, and jumps into the next function call
statement. If one base case is not defined, it will recur again and again, and store address into
stack. If the stack has no space anymore, it will raise an error as “Internal Stack Overflow”.
Example1: Find the factorial of a number n using recursion (i.e. direct recursion).
Algorithm:
Step 1: Start
Step 2: Read number n
Step 3: Call function fact(n)
Step 4: Print fact(f)
Step 5: Stop
fact(n)
Step 1: If n==1, then
return 1;
Step 2: Else
f=n*fact(n-1)
return f;
We can see that the factorial of a number n = n! is same as the n * (n-1)!, again it is same as
n * (n - 1) * (n - 2)!. So, if the factorial is a function, then it will be called again and again,
but the argument is decreased by 1. When the argument is 1, it will return 1. This could be
the base case of the recursion.
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Program Code: Recursive method to calculate factorial
public class FactorialExample
{
static int fact(int x)
{
if (x == 1)
return 1;
else
return x * fact(x - 1);
}
public static void main(String[] args)
{
int n = 3;
int res = fact(n);
[Link]("Factorial is: " + res);
}
}
Example2: WAP to print numbers from 1 to 10 in such a way that when number is odd, add
1 and when number is even, subtract 1, (i.e indirect recursion.)
Result: 2 1 4 3 6 5 8 7 10 9
Algorithm:
Step 1: Start
Step 2: Read n =1;
Step 3: Call function odd()
Step 4: Stop
odd()
Step 1: Start
Step 2: if n<=10, then
print n+1;
n++;
Call even ();
even()
Step 1: Start
Step 2: if n<=10, then
print n-1;
n++;
Call odd ();
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Program Code:
public class OddEvenExample
{
static int n = 1;
static void odd()
{
if (n <= 10)
{
[Link]((n + 1) + " ");
n++;
even();
}
}
static void even()
{
if (n <= 10)
{
[Link]((n - 1) + " ");
n++;
odd();
}
}
public static void main(String[] args)
{
odd();
}
}
Iteration:
Iteration is the repetition of a process in a computer program, usually done with the
help of loops. An example of an iteration programming language is as follows:
WAP in java to print the number from 1 to 10 using iteration
public class PrintNumbers
{
public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
[Link](i + " ");
}
}
}
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Difference between recursion and iteration
Property Recursion Iteration
A set of instructions
Definition Function calls itself. repeatedly executed.
Application For functions. For loops.
Through base case, where When the termination
there will be no function condition for the iterator
Termination call. ceases to be satisfied.
Used when code size Used when time complexity
needs to be small, and time needs to be balanced against
Usage complexity is not an issue. an expanded code size.
Code Size Smaller code size Larger Code Size.
Tail Recursion
A function is called tail-recursive if its recursive call is the final operation performed in
order to compute the return value.
A recursive function is said to be tail recursive if the recursive call is the last thing done
by the function. There is no need to keep record of the previous state.
A function call is said to be tail recursive if there is nothing to do after the function
returns except return its value. Since the current recursive instance is done executing at that
point, saving its stack frame is a waste. Specifically, creating a new stack frame on top of the
current, finished, frame is a waste.
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Example: tail recursion
public class TailRec
{
static int fact(int n)
{
if (n == 0)
{
return 1;
}
else {
[Link](" " + n);
}
return fact(n - 1); // tail recursive call
}
public static void main(String[] args)
{
fact(3);
}
}
Output:
Not tail recursion
A recursive function is said to be non-tail recursieve if the recursieve call not the last
thing done by the function. After returning back, there is some something left to evaluate.
Example:
public class NonTailRec
{
static int fact(int n)
{
if (n == 0)
{
return 1;
}
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
else {
fact(n - 1); // recursive call (not the last statement)
}
[Link](" " + n);
return 1; // required in Java
}
public static void main(String[] args) {
fact(3);
}
}
Output:
Fibonacci Series:
Fibonacci series generates the subsequent number by adding two previous numbers.
Fibonacci series starts from two numbers f0 & f1 the initial values of f0 & f1 can be taken 0, 1
or 1, 1 respectively.
Fibonacci series satisfies the following conditions:
fn = fn-1 + fn-2
Hence, a Fibonacci series can look like this
f8 = 0 1 1 2 3 5 8 13
or, this
f8 = 1 1 2 3 5 8 13 21
Algorithm: Recursive algorithm for Fibonacci Series
Step 1: Start
Step 2: Declare i and n
Step 3: for loop i to n
Call function fibonacci(i)
Display fibonacci(i)
end for loop
Step 4: Stop
fibonacci(int n)
Step 1: Start
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Step 2: if n<=1
Return n
Step 3: else
return fibonacci(n-1) + fibonacci(n-2)
end if
Program Code:
import [Link];
public class FibonacciSeries
{
// Recursive method to find Fibonacci number
static int fibonacci(int n)
{
if (n <= 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args)
{
int i, n, fib;
Scanner sc = new Scanner([Link]);
[Link]("Enter the number of elements in fibonacci series: ");
n = [Link]();
for (i = 0; i < n; i++)
{
fib = fibonacci(i);
[Link](fib + " ");
}
[Link]();
}
}
Output:
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Tower of Hanoi (TOH):
Tower of Hanoi is a mathematical puzzle which consists of three towers (pegs) and more than
one disks is as depicted. These disks are of different sizes and stacked upon in an ascending
order, i.e. the smaller one sits over the larger one. The objective of the puzzle is to move the
entire disks to another tower, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack i.e. a disk can only be moved if it is the uppermost disk on a
stack.
3. No disk may be placed on top of a smaller disk.
There are other variations of the puzzle where the number of disks increase, but the tower
count remains the same.
Tower of Hanoi puzzle with n disks can be solved in minimum 2 n – 1 Steps. This presentation
shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.
Algorithm: Recursive algorithm of tower of Hanoi.
Step 1: Start
Step 2: Create a function Hanoi(n, source, dest, aux)
Step 3: if disk == 1, THEN
move disk from source to dest
else
Hanoi(n - 1, Source, Aux, Dest)
move disk from source to dest
Hanoi(n - 1, Aux, Dest, Source)
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
end if
Step4: Stop
Program Code:
import [Link];
public class TowerOfHanoi
{
static void toh(int n, char source, char dest, char aux)
{
if (n == 1) {
[Link](source + " -> " + dest);
return;
}
toh(n - 1, source, aux, dest);
[Link](source + " -> " + dest);
toh(n - 1, aux, dest, source);
}
public static void main(String[] args)
{
char source = 'A', destination = 'B', auxiliary = 'C';
int n;
Scanner sc = new Scanner([Link]);
[Link]("Enter the number of disk: ");
n = [Link]();
// Call method (same order as C program)
toh(n, source, auxiliary, destination);
}
}
Explanation:
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
Application of recursion
There are many applications of recursion in real life examples. Recursion helps to solve the
problem need to execute same function again and again. Some of the common applications of
recursion are:
Solving ToH problem: we discussed in previous session
Solving Fibonacci Series problem: we discussed in previous session
Calculating factorial of given number: we discussed in previous session
Different Puzzle Games: like Candy Crush, Chess etc.
Searching Algorithms: like Search Tree
Sorting Algorithms: like Quick Sort, Merge Sort etc.
Teksan Gharti
BIM SEM - III
Data Structures & Algorithms
========================== End of Unit-5 ============================
Teksan Gharti