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