Data Structures and Algorithms - Old Questions

2. What do you mean by recursion? Explain the implementation of factorial and Fibonacci sequences with example.

Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result.

In order to solve a problem recursively, two conditions must be satisfied. First, the problem must be written in a recursive form, and second, the problem statement must include a stopping condition.

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

}

E.g.

A Fibonacci sequence is the sequence of integer in which each element in the sequence is the sum of the two previous elements.

Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

       Fn = Fn-1 + Fn-2

E.g.

F8 = 0,  1,  1,  2,  3,   8,  13  or, F8 = 1,  1,  2,  3,  5,  8,  13,  21

Program to generate Fibonacci series up to n terms 

#include<stdio.h>

#include<conio.h>

void main()

{

int n, i;

int fibo(int);

printf("Enter n:");

scanf("%d",&n);

printf("Fibonacci numbers up to %d terms:\\n",n);

for(i=1;i<=n;i++)

printf("%d\\n",fibo(i));

getch();

}

int fibo(int k)

{

if(k == 0 || k == 1)

return k;

else

return fibo(k-1)+fibo(k-2);

}