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.

ReplyDeletevalentino shoesle coq sportif chaussuresjordanslouis vuitton outletlouis vuitton ukpuma shoescoach outletcoach outlet onlinetommy hilfiger outletseattle seahawks jerseyschenlina20170227

ReplyDeletecoach outletcoach factory outlet onlineghd straightenerschristian louboutin shoesrolex replicachicago white sox jerseysyeezy boostmichael kors outletray ban sunglassescoach outlet20170321huazhen