Study Notes for Recursion
By BYJU'S Exam Prep
Updated on: September 25th, 2023
A function that calls itself directly or indirectly is called a recursive function. The recursive factorial function uses more memory than its non-recursive counterpart. The recursive function requires stack support to save the recursive function calls.
- Recursion leads to a compact
- It is simple
- It is easy to understand
- It is easy to prove correct
Table of content
- Recursion leads to a compact
- It is simple
- It is easy to understand
- It is easy to prove correct
1. Factorial Recursive Function
Factorial is denoted as n! which is given as
n! = n(n-1)(n-2)(n-3)…..(2)(1)
Example : 4! = 4*3*2*1 = 24
Recursive Program :
Fact(int n)
{
if(n==1)
return 1;
else
return n*Fact(n-1);
}
Recurrence Relation :
Time Complexity :
We can solve the above recurrence relation using substitution method as :
T(n) = n*T(n-1)
= n*(n-1)*T(n-2)
= n*(n-1)*(n-2)T(n-3)
.
.
.
= n(n-1)(n-2)(n-3)…..(2)(1)
= n!
hence time complexity = O(n!)
2. Fibonacci Number Recursive Function
Fibonacci series is given by 0,1,1,2,3,5,8,13…….
To calculate specific index in Fibonacci series , F(i) = F(i-1) + F(i-2);
Example : F(3) = F(2) + F(1) = 1 + 1 = 2
Recursive Program :
Fib(int n)
{
if(n==0)
return 0;
if(n==1)
return 1;
else
return fib(n-1) + fib(n-2);
}
Recurrence Relation :
Time Complexity :
The above recurrence relation can be solved using recursive tree method which will have maximum n-levels.
Total number of nodes = Total number of function calls = 2n
Hence time complexity = O(2n)
3. Minimum and Maximum value in array Recursive Function
We are given an array and we want to find out the maximum and minimum element in that array.
Recursive Program :
Recurrence Relation :
Time Complexity :
The above recurrence relation can be solved using substitution method as :
Hence if asked number of comparisons required to find min/max in array , then they are 3n/2 – 2.
Time Complexity = O(n)
4. Sum of ‘n’ numbers Recursive Function
Sum of n natural numbers from 1 to n is given as : 1 + 2 + 3 + …… n
Recursive Program :
int sum (int n)
{
int s;
if (n == 0)
return 0;
s = n + sum(n-1);
return s;
}
Recurrence Relation :
Time Complexity :
We can solve the above recurrence relation using substitution method as :
T(n) = n+T(n-1)
= n+(n-1)+T(n-2)
= n+(n-1)+(n-2)T(n-3)
.
.
.
= n+(n-1)+(n-2)+(n-3)…..(2)+(1)
= 1 + 2 + 3 +…….n
= n(n+1)/2
hence time complexity = O(n^2)
5. Ackermann’s Relation
Ackermann’s relation is an example of nested recursion in which there are recursive calls inside a recursive call.
Recursive Program :
int Ackermann(int m , int n)
{
if(m==0)
return (n+1);
else if(n==0)
return Ackermann(m-1,1)
else
return Ackermann(m-1,Ackermann(m,n-1));
}
Recurrence Relation :
So that’s all about recursion and some commonly used recursive functions.
Click Here to Avail GATE CSE Test Series!
Thanks
#DreamStriveSucceed
