CS 478: Design and Analysis of Algorithms
Recursive
Algorithm Analysis
Fall 2024
Mr. Ahsan Shah
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Objectives
• Become familiar with the idea of recursion
• Learn to use recursion as a programming tool
• Analyze the time complexity of recursive
algorithms.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Overview
Recursion: a definition in terms of itself.
Recursion in algorithms:
• Natural approach to some (not all) problems
• A recursive algorithm uses itself to solve one or more
smaller identical problems
• Recursive methods implement recursive algorithms
• A recursive method includes a call to itself
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Recursive Methods
Must Eventually Terminate
A recursive method must have
at least one base, or stopping, case.
• A base case does not execute a recursive call
– stops the recursion
• Each successive call to itself must be a "smaller version of itself”
– an argument that describes a smaller problem
– a base case is eventually reached
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Key Components of a Recursive Algorithm Design
1. What is a smaller identical problem(s)?
● Decomposition
2. How are the answers to smaller problems combined to form the
answer to the larger problem?
● Composition
3. Which is the smallest problem that can be solved easily
(without further decomposition)?
● Base/stopping case
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Examples in Recursion
• Usually quite confusing the first time
• Start with some simple examples
– factorial
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
Factorial (N!)
• N! = (N-1)! * N [for N > 1]
• 1! = 1
• 3!
= 2! * 3
= (1! * 2) * 3
=1*2*3
• Recursive design:
– Decomposition: (N-1)!
– Composition: * N
– Base case: 1!
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
factorial Method
public static int factorial(int n)
{
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; // composition
else // base case
fact = 1;
return fact;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
public static int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return fact;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
public static int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return 1;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = 1 * 2;
else
fact = 1;
return fact;
}
public static int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return 1;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = 1 * 2;
else
fact = 1;
return 2;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = 2 * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = 1 * 2;
else
fact = 1;
return 2;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis of Algorithms
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = 2 * 3;
else
fact = 1;
return 6;
}
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(decomposition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(decomposition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
factorial(2) 3
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(decomposition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
factorial(2) 3
factorial(1) 2
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3) 4
*
factorial(2) 3
*
factorial(1)->1 2
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3) 4
*
factorial(2)->2 3
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3)->6 4
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS 478: Design and Analysis
public static of Algorithms
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)->24
Time Complexity= O(n)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
