Lecture 7: Recurrence and Recursions
By Dr. Milad Ahmed Elgargni
Recurrence and Recursions
Definitions
1. Recurrence refers to a mathematical equation or formula that defines a sequence of numbers or values.
These equations describe how each term in the sequence is related to previous terms. Recurrence
relations are commonly used in the analysis of algorithms.
2. Recursion on the other hand, refers to the process in which a function calls itself in order to solve a
smaller instance of the same problem. This technique is often used in programming to solve problems
that can be broken down into smaller, similar sub-problems. For example, divide and conquer method.
// This program to show recurrence
Test (3) One call // relation work.
#include <iostream>
3 Test (2) One call using namespace std;
void test(int n){
2 Test (1) One call
if (n>0){
cout<<"\n n = "<< n;
1 Test (0) One call
test(n-1);
}
Stop }
Recursive tree int main (){
test(3);
cout<<"\n ";
n executed however just 3 + 1 calls }
So, F(n) = n + 1 O (n) 3 is passed to the function
Figure 1 Recurrence and recursion principal
Recursion and Recurrence relations
Time complexity of
( ) {
( )
Recurrence relation
Since ( ) ( ) (1)
So, by substituting n in T(n - 1) by ( ) we get the equation 2
T(n - 1) = T(n -1 - 1) + 1 = T(n – 2) + 1 (2)
Then, by substitute n in T(n – 2) by ( ) we get the equation 3
T(n - 2) = T(n - 1 - 2) + 1 = T(n - 3) + 1 (3)
Now by substituting T(n – 1) in equation 1 by T(n - 2) + 1 yields equation 4
T(n) = T(n - 2) + 2 (4)
Now by substituting T(n – 2) in equation 4 by T(n -3) + 1 in equation 1 yields equation 5
T(n) = T(n - 3) + 3 (4)
1
Lecture 7: Recurrence and Recursions
By Dr. Milad Ahmed Elgargni
.
.
.
Continue up to k we get
T(n) = T(n - k) + k
Now we assume
n–k=0
n=k
T(n) = T(n - n) + n
T(n) = T(0) + n
T(n) = 1 + n ~ O(n)
int Factorial(int n){
if (n > 0){
return n * Factorial(n - 1);
} .
else
return 1;
.
} .
Figure 2: Illustrates Recursion and Recurrence Relations
//This program calculates a factorial of a number
#include <iostream>
using namespace std;
int Factorial(int n){
if (n == 0){
return 1;
}
else
return n * Factorial(n - 1);
}
int main ()
{
int n;
cin>>n;
cout<<" The factorial of "<<n <<" is "<< Factorial(n);
cout<<"\n";
}
2
Lecture 7: Recurrence and Recursions
By Dr. Milad Ahmed Elgargni