Write a function to calculate the nth Fibonacci Sequence is a common interview question and often the solution is something like
int Fib(int n)
{
if(n < 1) return 1;
return Fib(n-1) + Fib(n-2);
}
The next question is to ask for n=100, how many items will be on the stack. The answer is not 100 but actually horrible! It is closer to 2^100.
take the first call – we start a stack on Fib(99) and one on Fib(98). There is nothing to allow Fib(99) to borrow the result of Fib(98). So one step is two stack items to recurse. Each subsequent call changes one stack item into 2 items. For example
- 2 –> call [Fib(1), Fib(0)]
- 3 –> calls [ Fib(2)->[Fib(1), Fib(0)], Fib(1) –> Fib(0) ]
- 4 –> calls [ Fib(3)->[[[ Fib(2)->[Fib(1), Fib(0)], Fib(1) –> Fib(0) ]], Fib(2)->[Fib(1), Fib(0)], Fib(1) –> Fib(0) ]
Missing this issue is very often seen with by-rote developers (who are excellent for some tasks).
A better solution is to cache the values as each one is computed – effectively creating a lookup table. You are trading stack space for memory space.
Placing constraints on memory and stack space may force the developer to do some actual thinking. A solution that conforms to this is shown below
private static long Fibonacci(int n) {
long a = 0L;
long b = 1L;
for (int i = 31; i >= 0; i—) //31 is arbitrary, see below
{
long d = a * (b * 2 - a);
long e = a * a + b * b;
a = d;
b = e;
if ((((uint)n >> i) & 1) != 0) {
long c = a + b;
a = b;
b = c;
}
}
return a;
}
The output of the above shows what is happening and suggests that the ”31” taking the log base 2 of N can likely be done to improve efficiency
for 32:
for 65
for 129
What is the difference in performance for the naive vs the latter?
I actually did not wait until the naive solution finished… I aborted at 4 minutes
The new improved version was 85 ms, over a 3000 fold improvement.
Take Away
This question:
- Identify if a person knows what recursion is and can code it.
- Identify if he understands what the consequence of recursion is and how it will be executed(i.e. think about what the code does)
- Most recursion questions are atomic (i.e. factorial) and not composite (recursion that is not simple)
- Is able to do analysis of a simple mathematical issue and generate a performing solution.
Posts
