C program to compute the fibonacci series using recursion

      Whenever solution to the problem is approached with recursive fashion, the solution to that problem is decomposed into a certain number of small tasks (i.e., recursive calls) which together gives a complete solution. These recursive calls stop at one particular condition that condition is called as base condition. So every recursive function needs two criteria. One is base criteria and another one is recursive criteria. In this program the recursive criteria is ‘Fib(val-1) + Fib(val-2)’ which computes the value and the base criteria is ‘if(val==1 || val==2) return 1’ which supplies value to the recursive call. In this way, we determine fibonacci series using recursion.

fibonacci series using recursion program in c



Source Code :

#include<stdio.h>
#include<stdlib.h>
int fib(int); 
int main()
{
    int i,j;
    printf("\n Enter the number of terms: "); 
    scanf("%d",&i);     //Step 1
    if(i < 0)
     {
       printf("\n Error - Number of terms cannot be negative\n");
       exit(1);
     }
     printf("\n Fibonacci sequence for %d terms is: ",i);
     for( j=1; j<=i; ++j)
     printf(" %d",fib(j));   //Step 2
     return 0;
}
int fib(int val)
{
    if(val == 1||val==2)       //Step 3
	return 1;
    else
	return(fib(val - 1) + fib(val - 2)); //Step 3(i)
}


edit-code-image

Sample Test cases:

1. Enter the number of terms: 4
   Fibonacci sequence for 4 terms is:  1 1 2 3

2. Enter the number of terms: -2
   Error - Number of terms cannot be negative.

Explanation:

Step 1 : The number of terms is read from the user using scanf() function.

Step 2 : The function fib() is called from the main program.

Step 3 : This base condition returns ‘1’ if the value of ‘val’ is either 1 or 2.

Step 3(i): The recursive function ‘fib(val-1) + fib(val-2)’ helps to evaluate the value after evaluation of base condition.

More Insights:

1. More about execution of recursive function.

1. Explanation of recursive function execution (video).

More Content : Explore More