Study notes for recursion

         

A function that calls itself directly or indirectly is called a recursive function. The recursive factorial function uses more memory than its non-recursive counter part. Recursive function requires stack support to save the recursive function calls.

• Recursion leads to 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 = 2ⁿ
Hence time complexity = O(2ⁿ)

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.

Thanks,