Design and Analysis of Algorithm (DAA)
Analysis of Recursive Algorithms
[Module 1]
Dr. Dayal Kumar Behera
School of Computer Engineering
KIIT Deemed to be University, Bhubaneswar, India
OSGN - OSPN [1]
Recursion
• Recursion is a method of solving a computational problem where the
solution depends on solutions to smaller instances of the same
problem.
• The process in which a function calls itself directly or indirectly is called
recursion and the corresponding function is called a recursive function.
Each branch can be seen as a smaller version of a tree.
OSGN - OSPN Image Source: Wikipedia [2]
Types of Recursion
Single recursion/Linear recursion:
• Recursion that contains only a single self-reference
• Single recursion can be further classified into:
• Tail recursion: recursive call is the last statement
executed within the function
• Head recursion: recursive call occurs before any
other operation within the function.
Multiple recursion/Tree recursion:
• Recursion that contains multiple self-references.
OSGN - OSPN [3]
Single Recursion
fun(n)
{
// some code
if(n>0)
{
fun(n-1); // Calling itself only once
}
// some code
}
OSGN - OSPN [4]
Tail Recursion
// Recursion function Last statement is the recursive call.
void fun(int n)
{
if (n > 0) {
printf("%d ", n);
fun(n - 1);
}
}
Output for fun(3)
321
OSGN - OSPN Image Source: geeksforgeeks [5]
Tail Recursion: Equivalent Loop
// Recursion function // Equivalent Loop
void fun(int n) void fun(int n)
{ {
if (n > 0) { while (n > 0) {
printf("%d ", n); printf("%d ", n);
fun(n - 1); n--;
} }
} }
OSGN - OSPN [6]
Tail Recursion: Time Complexity
// Recursion function // Equivalent Loop
void fun(int n) void fun(int n)
{ {
if (n > 0) { while (n > 0) {
printf("%d ", n); printf("%d ", n);
fun(n - 1); n--;
} }
} }
Recurrence equation Solving by step count method, the time
complexity is linear: O(n).
T(n) = T(n-1) + 1, T(1) = 1
Solving the above recurrence, the time
complexity is linear: O(n).
OSGN - OSPN [7]
Tail Recursion: Space Complexity
// Recursion function // Equivalent Loop
void fun(int n) void fun(int n)
{ {
if (n > 0) { while (n > 0) {
printf("%d ", n); printf("%d ", n);
fun(n - 1); n--;
} }
} }
Each recursive call adds a new Regardless of the input value of n, the
frame to the call stack, consuming memory usage remains constant.
memory.
space complexity is O(1) (constant space).
Since there will be exactly n
recursive calls (from n down to 1),
the space complexity is O(n)
(linear space).
OSGN - OSPN [8]
Head Recursion
// Recursion function first statement is the recursive call.
void fun(int n)
{
if (n > 0) {
fun(n - 1);
printf("%d ", n);
}
}
Output for fun(3)
123
OSGN - OSPN Image Source: geeksforgeeks [9]
Head Recursion: Equivalent Loop
// Recursion function
void fun(int n)
{
if (n > 0) {
fun(n - 1);
printf("%d ", n);
}
}
Unlike Tail recursion, in head recursion the conversion is not easy.
// Wrong Output // Equivalent Loop
void fun(int n) void fun(int n)
{ {
while (n > 0) { int i=1;
n--; while (i <= n) {
printf("%d ", n); printf("%d ", i);
} i++;
} }
}
OSGN - OSPN [10]
Head Recursion: Time Complexity
// Recursion function // Equivalent Loop
void fun(int n) void fun(int n)
{ {
if (n > 0) { int i=1;
fun(n - 1); while (i <= n) {
printf("%d ", n); printf("%d ", i);
} i++;
} }
}
Recurrence equation Solving by step count method, the time
complexity is linear: O(n).
T(n) = T(n-1) + 1, T(1) = 1
Solving the above recurrence, the time
complexity is linear: O(n).
OSGN - OSPN [11]
Head Recursion: Space Complexity
// Recursion function // Equivalent Loop
void fun(int n) void fun(int n)
{ {
if (n > 0) { int i=1;
fun(n - 1); while (i <= n) {
printf("%d ", n); printf("%d ", i);
} i++;
} }
}
Each recursive call adds a new The function fun contains only one extra
frame to the call stack, consuming integer variable: i.
memory. Regardless of the input value n, the
Since there will be exactly n memory used for i remains the same.
recursive calls (from n down to 1), There are no data structures (arrays, lists,
the space complexity is O(n) etc.)
(linear space).
space complexity is O(1) (constant space).
OSGN - OSPN [12]
Tree Recursion
// Recursion function
void fun(int n){ recursive call more than once in the code.
if (n > 0) {
printf("%d ", n); Output for fun(3)
fun(n - 1); 3211211
fun(n - 1);
}}
No. of function call
1
OSGN - OSPN Image Source: geeksforgeeks [13]
Tree Recursion: Equivalent Loop
// Recursion function
void fun(int n){
if (n > 0) {
printf("%d ", n);
fun(n - 1);
fun(n - 1);
}
}
Unlike Tail recursion and head recursion, here the direct
conversion may not be possible.
OSGN - OSPN [14]
Time Complexity
// Recursion function
In recursion, time complexity depends on void fun(int n){
number of function call. if (n > 0) {
printf("%d ", n);
In this example, total function call for n=3 fun(n - 1);
1 + 2 + 4 + 8 = 15 fun(n - 1);
}
2^0 + 2^1 + 2^2 + 2^3 = (2^(n+1))-1 = O(2^n) }
Recurrence equation
T(n) = T(n-1) + T(n-1) + 1, T(1) = 1
Solving the above recurrence, the time
complexity is exponential: O(2^n).
OSGN - OSPN [15]
Solving the recurrence
Let us solve the following recurrence using iterative method
T(n) = T(n-1) + T(n-1) + 1, T(1) = 1
Recurrence Relation: T(n) = 2T(n-1) + 1
Iterative Solution:
• We’ll use an iterative approach to find a pattern.
• Start with the base case: (T(1) = 1).
• Then compute (T(2)), (T(3)), and so on:
T(2) = 2T(1) + 1 = 2 + 1 = 3
T(3) = 2T(2) + 1 = 2 * 3 + 1 = 7
T(4) = 2T(3) + 1 = 2 * 7 + 1 = 15
T(5) = 2T(4) + 1 = 2 * 15 + 1 = 31
General Pattern:
T(n) = 2^n - 1
Solving the above recurrence, the time complexity is exponential T(n) = 2^n – 1 = O(2^n).
OSGN - OSPN [16]
Space Complexity
• When analyzing space complexity, we // Recursion function
consider the memory used by the call stack void fun(int n){
if (n > 0) {
during the execution of the recursive printf("%d ", n);
function. fun(n - 1);
fun(n - 1);
• Each recursive call creates a new stack frame }
(activation record) with local variables and }
return addresses.
• The depth of the recursion tree is (n), as
each level corresponds to decrementing (n)
by 1.
• The maximum number of active function
calls (stack frames) at any point during
execution is the depth of the recursion tree.
• Therefore, the space complexity is O(n).
OSGN - OSPN [17]
Thank you
OSGN - OSPN [18]
