Showing posts with label fibonacci numbers. Show all posts
Showing posts with label fibonacci numbers. Show all posts

Sunday, January 5, 2014

Comparison of iterative and recursive way of Fibonacci Sequence calculation

The Fibonacci numbers are the sequence of numbers

$\{F_n\}_{n=1}^\infty$

defined by the linear recurrence equation

$$F_n = F_{n-1} + F_{n-2}$$

with $F_1 = F_2 = 1$, and conventionally defining $F_0 = 0$.

We can implement Fibonacci numbers by iteratively or by using recursion. These two functions are implemented in Matlab to compare the running time of the algorithms.

function [result] = fibonacciRecursive(n)
%calculates the fibonacci output in recursive way
    if n==0 || n==1
        result=1;
    else
        result=fibonacciRecursive(n-1)+ fibonacciRecursive(n-2);
    end
end


function [result] = fibonacciIterative( n )
%calculates the fibonacci output in iterative way
    y1=1;
    y2=2;
    for i=2:n
        result=y1+y2;
        y2=y1;
        y1=result;
    end
end
For testing:

N=10;

fibonacciIter=zeros(N,1);
fibonacciRecur=zeros(N,1);

for i=1:N
     tic
        for j=1:25
            fibonacciIterative(i);
        end
     
      fibonacciIter(i)=toc;
     
      tic
        for j=1:25
            fibonacciRecursive(i);
        end
      fibonacciRecur(i)=toc;
end
X=1:N;
plot(X,fibonacciIter,X,fibonacciRecur);
legend('Iterative', 'Recursive')
xlabel('input size');
ylabel('time(seconds)');
The plot is:

As shown in plot recursive implementation is increasing exponentially in time with the given input size