nth term in Fibonacci series recursive and iterative - UCS - Unleash-Coding-Skills

Sunday, 25 March 2018

nth term in Fibonacci series recursive and iterative - UCS




Fibonacci Series:

what is fibonacci series:

 In mathematic, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:


The sequence Fn of Fibonacci numbers is defined by the recurrence relation:
{\displaystyle F_{n}=F_{n-1}+F_{n-2},}
{\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots }
         {\displaystyle F_{0}=0,\;F_{1}=1.}

Iterative Solution:

#include <stdio.h>


int main()
{
int a=0,b=1,c=1,n,i;
scanf("%d",&n);
if(n==0)
printf("%d",a);
else if(n==1)
printf("%d",b);
else
{
for(i=2;i<=n;i++)
{
c=a+b;
a=b;
b=c;
}
printf("The %d term is %d",n,c);
}
return 0;

Input :4

Output: 

        The 4 term is 3

Recursive Solution:

 #include<stdio.h>
int fib(int n)
{
if (n <= 1)
    return n;
return fib(n-1) + fib(n-2);
}

int main ()
{
int n = 4;
printf(
The %d term is %d",n,fib(n));
return 0;
}

Input :4

Output: 

        The 4 term is 3

Recurssive tree for fibonacci series


          Image result for fibonacci recursive tree
 
The recursive solution is simple the recursion continues until the input parameter  value is 0 or 1.Then it will return 0 or 1 based on input and it will be
added to recursion call location so you can clearly see in recursion tree the sum at the child node is added at current parent node and this process continues until the summing reaches to the root of the recursion tree and it will be the output of our input.

Happy Coding....

No comments:

Post a comment