Monday, November 23, 2015

Recursion in programming

Recursion is a very useful programming technique. It can be simply described as calling the function by the same function. It can be understood better by examples rather than by definitions. 

A recursive algorithm must have the following,
  1. Base Case (to stop recursive call at some point)
  2. Recursive Call

Finding factorial of a positive integer.

The factorial of a positive integer is multiplication of a series of descending natural numbers.
4! = 4 x 3 x 2 x 1

In the above example note the following property.

4! = 4 x (3 x 2 x 1)
4! = 4 x 3!

Therefore for any positive integer n,
n! = n x (n-1)!

The above property enables us to use recursion.
If we write a function to find the factorial of a positive integer, let's call it 'factorial(int number)',
factorial(n) = n x factorial(n-1);
This is the recursive call. 

The base case is the factorial of 1. 
factorial(1) = 1;

Following is a program written in C to find factorial using a recursive algorithm.


#include <stdio.h>

int main()

      int number;
      printf("Enter an ineger: ");
      printf("The factorial is %d",factorial(number));

      return 0;


int factorial(int number)

      if(number == 1)
            return 1;

      return number*factorial(number-1);