facebook like button

12 September, 2011

getting nth term of fibonacci series using recursion

The need: 
     This program is written just to give example of writing programs with recursion. This program finds nth term of a fibonacci series. Given that first term is 1, second term is also 1 and for rest terms T(n)=T(n-1) + T(n-2) holds true.
The code: 
---------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
int fibo(int x);

int main()
{
    int n,Tn;
    printf("Enter which term do you want?\n");
    scanf("%d",&n);
    if(n>0)
    Tn=fibo(n);
    else
    exit(printf("term index entered should be natural number\n"));
    printf("T(%d) of fibonacci series = %d\n",n,Tn);
    return 0;
}

int fibo(int x)
{
    int term;
    if(x==1)
      term=1;
    else if(x==2)
      term=1;
    else
      term= fibo(x-1) + fibo(x-2);
    return term;
}
---------------------------------------------------------
Remarks:
1. This program may not give correct output if the desired term is after 40th term. This is because the later terms can not fit into int data-type of C and data overflows.
2. This type of recursion when one function calls 2 instances of itself, is called binary recursion.
3. This program was written just to show use of binary recursion. Personally I would suggest not to use a recursion which calls 2 or more instances because not only it uses more system resources but also slows down the program execution drastically. For fibonacci series without recursion see program38 of this blog.

No comments:

Post a Comment

feel free to ask your doubts... if any
you can post your doubts on
www.facebook.com/programsimply