CS378: Design and Analysis of Algorithms
Recursive
Algorithm Analysis
Mr. Salman Ashraf
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: 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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Designpublic static
and Analysis int factorial(int n)
of Algorithms
{
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
CS378: Design and Analysis of Algorithms
Fibonacci Algorithm
fib(n) = fib(n-1) + fib(n-2)
Time Complexity = O 2 𝑛
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Fibonacci Algorithm
fib(n) = fib(n-1) + fib(n-2)
Time Complexity = O 2 𝑛
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi