# Study Notes for Recursion

By Mukesh Kumar|Updated : December 4th, 2021

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
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

## 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.
So we use recursive function to get these values.

### Recursive Program :

int mid, leftmax, rightmax;
int max (int a[], int low, int high)
{
if (low == high)
return a[low];
else
{
mid = (low + high) / 2;
leftmax = max (a, low, mid);
rightmax = max (a, mid + 1, high);
if (leftmax > rightmax)
return leftmax;
else
return rightmax;
}
}

### 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. GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com