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


No comments:

Post a Comment