# Progressive Fibonacci

*In which our protagonist codes up the simplest thing that could possibly work*

*Hey Protagonist, gimme a function calculating and returning N-th Fibonacci number.*

Here you go:

```
def fib(n):
if n == 0 or n == 1:
return n
return fib(n - 2) + fib(n - 1)
```

*Hey, it crashes if I give it a non-natural number, that shouldn't happen. It should nicely report the error instead.*

Okay, no problem, here's a modified version:

```
def fib(n):
if (type(n) != int and type(n) != long) or n < 0:
raise ValueError('n should be a non-negative integer')
if n == 0 or n == 1:
return n
return fib(n - 2) + fib(n - 1)
```

*Hmm, it's really slow for, like, N = 50.*

Yeah, it's exponential. Here's an improved version that caches the intermediate results so they don't need to be recomputed:

```
def fib(n, cache={}):
if (type(n) != int and type(n) != long) or n < 0:
raise ValueError('n should be a non-negative integer')
if n == 0 or n == 1:
return n
if n not in cache:
cache[n] = fib(n - 2) + fib(n - 1)
return cache[n]
```

*WTF ?!*

Okay, okay, exploiting mutability of default arguments in Python is kinda evil. Here's a more readable version:

```
def fib(n):
if (type(n) != int and type(n) != long) or n < 0:
raise ValueError('n should be a non-negative integer')
cache = {}
def f(n):
if n == 0 or n == 1:
return n
if n not in cache:
cache[n] = f(n - 2) + f(n - 1)
return cache[n]
return f(n)
```

*Umm, I'm tight on space on this device, can it use a constant amount of memory?*

Sure, here you go [0]:

```
def fib(n):
if (type(n) != int and type(n) != long) or n < 0:
raise ValueError('n should be a non-negative integer')
a, b = 0, 1
for i in xrange(n):
a, b = b, a + b
return a
```

*Cool! That solves it! Umm, I only actually ever need to calculate first 20 Fibonacci numbers...*

No worries, use this:

```
def fib(n):
seq = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
try:
return seq[n]
except IndexError:
return ValueError('n is out of bounds')
```

Which implementation is the best? The answer will shock you - *all of them!* (well, except maybe the evil one). Each implementation addresses all of the requirements put forth so far in the dialogue.

If you've chosen any of the above as "the best", you've added a few of your own unstated, undocumented, unchecked assumptions about the requirements into the mix. Don't do that.

Do the simplest thing that could possibly work[1].

*PS. Not related to the discussion, but definitely related to Fibonacci, is a comment over at reddit describing Fast Fibonacci Transform, a method for calculating N-th Fibonacci number in logarithmic time, well worth a read.*

[0] I cheated a bit, as this is clearly simpler than the previous versions. If only real-world problems would be as discernible as generating Fibonacci numbers!

[1] Where "work" is defined as "satisfy all the explicit requirements".

A practitioning bit-shifting magician turned cat herder.