nth Fibonacci Number: sample solution

Recursive solution

Here is a solution using recursion, in other words, using a function that calls itself. We define the two base cases (if n==1 or if n==2) and then we define the output using a recursive call to the function itself.

This is a nice trick and a benefit is that it has a close resemblance to the mathematical definition of the nth Fibonacci number.

function f = Fib_r(n)

if n==1
    f=1;
elseif n==2
    f=2;
else
   f = Fib_r(n-1) + Fib_r(n-2); 
end

end

The downside of a recursive solution like this is that for large values of the input n, we end up with exponentially higher numbers of function calls to Fib_r() in order to generate the solution. Here is a video and an interactive web demo that shows how this works.

One way to improve the performance of a recursive approach is to use a technique called memoization. The idea is to cache (e.g. store in a global variable) the solutions to sub-problems as they are solved, so that when those specific sub-problems have to be solved again, they can be looked up, in the lookup-table, rather than actually re-solved using another series of recursive calls. Essentially it trims entire branches of the recursion tree.

Iterative solution

Here’s how we could approach this using an iterative solution that doesn’t involve recursion:

function f = Fib_i(n)

if n==1
    f=1;
elseif n==2
    f=2;
else
    ff = [1,2];
    for i=3:n
       ff = [ff(2), ff(1)+ff(2)]; 
    end
    f = ff(2);
end

end

We can time the function execution using tic and toc in MATLAB, to visualize how much more efficient the iterative solution Fib_i()is compared to the recursive solution Fib_r():

fprintf('for n=15\n');
tic; Fib_i(15); toc
tic; Fib_r(15); toc
fprintf('for n=30\n');
tic; Fib_i(30); toc
tic; Fib_r(30); toc
fprintf('for n=45\n');
tic; Fib_i(45); toc
tic; Fib_r(45); toc

On my machine I get the following output:

for n=15
Elapsed time is 0.000080 seconds.
Elapsed time is 0.000082 seconds.
for n=30
Elapsed time is 0.000056 seconds.
Elapsed time is 0.032039 seconds.
for n=45
Elapsed time is 0.000065 seconds.
Elapsed time is 43.609629 seconds.

So for small input values of n like n=10 there isn’t much of a difference, they are both very fast. But by the time we get to n=45, the iterative solution is only slightly slower but the recursive solution is more than 67,000 x slower than the iterative solution! As n increases, the time of the iterative solution only increases linearly while the time for the recursive solution increases exponentially. This is a concept in computer science called time complexity and you may come across Big-O notation which is used to describe the complexity of algorithms.