## Interview Questions

### Implement fibonnaci function

Explain performance of your solution when compared with recursive version.

View Solution

#### Overview

This problem is relatively simple however there are two main solutions to the problem. One relies on actual definition of Fibonacci numbers:

f(n) = f(n-1) + f(n-2)

This approach is easiest to implement however its computational complexity is very high (exponential) as we will be calculating same values all time.

One of the potential ways to improve on this solution is to use hashtables and recursive approach and store numbers calculated in hashtable.

The best approach is however to notice that each number is calculated from always two previous numbers and knowing this implement this solution iteratively.

#### Complexity

Computational complexity of this algorithm differs between recursive and iterative solution. In case of recursive solution, because there is lots of repetition for calculating the same value, the complexity is exponential. In case of iterative approach the complexity is O(n).

#### Solution - iterative

//
// f(n) = f(n-1) + f(n-2)
//
long fib(int n)
{
long nMinus2 = 0; // f(0)
long nMinus1 = 1; // f(1)
long result = 1;
// error condition
if (n < 0) return -1;
// base values
if (n == 0) return 0;
if (n == 1) return 1;
// this starts usually from 2
for (int i = 2; i <= n; i++)
{
result = nMinus1 + nMinus2;
nMinus2 = nMinus1;
nMinus1 = result
}
return result;
}

#### Solution - recursive

####
long fib(int n)
{
if (n < 0) return -1;
// error condition
if (n < 0) return -1;
// base values
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}

#### External Resources