Data Structures and Algorithms - Old Questions

7. Define recursive algorithm? How do you implement recursive algorithms while writing computer programs?

A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input.

We can use following steps to implement recursive algorithm:

1. Initialize the algorithm. Recursive programs often need a seed value to start with. This is accomplished either by using a parameter passed to the function or by providing a gateway function that is nonrecursive but that sets up the seed values for the recursive calculation.
2. Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4. Run the algorithm on the sub-problem.
5. Combine the results in the formulation of the answer.
6. Return the results.

For e.g.

Program to find factorial of an integer:

#include<stdio.h>

#include<conio.h>

void main( )

{

clrscr( );

 int factorial(int);

 int n,f;

 printf("Enter the number: ");

 scanf("%d",&n);

 f=factorial(n);

 printf("Factorial of the %d number is %d",n,f);

 getch();

}

int factorial(int n)

{

  int f;

  if(n==1)

     return 1;

  else

     f=n*factorial(n-1);

     return f;

}