If you've ever done a tech interview, you're probably familiar with the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, ....

where each number is the sum of the previous two. A relatively simple (and relatively overused) interview problem is to write a function that returns the n-th Fibonacci number.

## Recursive Python

The most intuitive implementation is recursive:

``````def fib(n):
"""the profoundly inefficient recursive implementation"""
if n in [0, 1]:
return 1
else:
return fib(n - 1) + fib(n - 2)
``````

It works in a pretty obvious fashion.

``````>>> map(fib, range(10))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
``````

However, it's shockingly inefficient. To compute `fib(10)` we need to compute `fib(9)` and `fib(8)`. To compute `fib(9)` we need to compute `fib(8)` (again) and `fib(7)`. And so on.

The moral of the story is that to compute `fib(10)` we end up making 177 calls to `fib`. To compute `fib(20)` we end up making 21,891 calls to `fib`. And to compute `fib(30)` we end up making 2.7 million calls to `fib`, which ends up taking almost a full second on my laptop.

One solution is memoization, in which we remember previously computed values. We won't get into that here.

## Iterative Python

Another solution is an iterative approach:

``````def fib(n):
"""the iterative implementation"""
x, y = 0, 1
for _ in range(n):
x, y = y, x + y
return y
``````

This is much more efficient -- to compute `fib(n)` we just do O(n) operations. At the same time, it's much less clear what it's actually computing. If I didn't tell you it was `fib` you might have to stare at it for a while to figure out exactly what it was doing. And even knowing that it's `fib` it's probably not obvious that it's implemented correctly.

Haskell, in case you don't know, is everyone's favorite pure functional programming language. In particular, it embraces laziness in which values are computed only as needed.

This means we can compute the (infinite) sequence of Fibonacci numbers as

``````fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Prelude> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]
``````

You should understand this definition as "the sequence that starts with 1, followed by 1, followed by the sequence of numbers obtained by "zipping" together the sequences `fibs` and `tail fibs` (that is, all of the elements of `fibs` after the first) and adding together each corresponding pair of elements.

Which means the third element of the sequence is the first element (of `fibs`) plus the second element (which is the first element of `tail fibs`). The fourth element is the second element (of `fibs`) plus the third element (which is the second element of `tail fibs`). And so on. This is precisely the definition of Fibonacci.

This definition may seem circular, since we're using `fibs` to define `fibs`.

After all, the following sort of thing leads to infinite recursion:

``````def fibs(x=0, y=1):
return [y] + fibs(y, x+y)

>>> fibs()[0]
....
RuntimeError: maximum recursion depth exceeded
``````

But in the Haskell version, because of laziness, the elements of `fibs` will only be evaluated as needed. To compute the third element, we only need to know the first two elements, which we already do by the time we're trying to compute the third element, and so on.

Appreciate its stark, mathematical beauty! (Learn Haskell!)

## Laziness in Python

We can achieve laziness in Python using generators. One way is list comprehensions in parentheses.

``````>>> num = (i for i in range(3))
>>> num
<generator object <genexpr> at 0x7f5efc33bd70>
>>> num.next()
0
>>> num.next()
1
>>> num.next()
2
>>> num.next()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
``````

Each element of `num` is computed only on demand.

We can also use functions with `yield`:

``````>>> def to3():
...   yield 1
...   yield 2
...   yield 3
...
>>> [x for x in to3()]
[1, 2, 3]
``````

This is how we'll implement the Haskell-style Fibonacci.

## itertools

The Haskell implementation used `tail` (to get the elements after the first) and `take` (to get a certain number of elements from the front). Python doesn't have those, so we'll need to implement our own versions.

The `itertools` module contains some helpers for working with laziness. We'll need `islice` which allows us to slice a new generator out of an old one.

``````from itertools import islice

def tail(iterable):
"""return elements from 1 to forever"""
return islice(iterable, 1, None)

def take(n, iterable):
"""return elements from 0 to n in a list"""
return list(islice(iterable, 0, n))
``````

For our Python 2.7 version we'll also need `imap`, which is simply the lazy version of `map`.

As a warmup, let's create an infinite sequence using the iterative approach:

``````def fibs():
x, y = (0, 1)
while True:
yield y
(x, y) = (y, x + y)
``````

Which we can use like:

``````>>> take(10, fibs())
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
``````

``````fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
``````

It's not hard to create the Python 2.7 equivalent

``````from itertools import imap   # lazy map

def fibs():
yield 1
yield 1
for n in imap(add, fibs(), tail(fibs())):
yield n
``````

The logic is exactly the same. The first two elements both equal 1. After that we lazily add together the corresponding elements of `fibs()` and of `tail(fibs())`:

``````>>> take(10, fibs())
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
``````

In Python 3.3+, this gets even simpler. First `map` is already lazy, so there's no reason to use `imap`. And second, 3.3 introduces `yield from` which allows us to replace the clunky

``````for x in xs:
yield x
``````

with

``````yield from xs
``````

This means that the Python 3.3+ implementation is simply:

``````def fibs():
yield 1
yield 1
``````

Which we could one-line as

``````def fibs(): yield 1; yield 1; yield from map(add, fibs(), tail(fibs()))
``````

More on this in a second.

## Warning!

Despite appearing Haskell-like, this version is basically as inefficient as the original recursive version. That's because every time `fibs()` is called recursively, Python redoes from scratch all the work to generate the sequence.

Whereas in Haskell things are immutable, which means that there's only a single `fibs` hanging around. Once its first few elements have been computed, they never have to be computed again.

So while our Python version is clever, it's also impractical.

## A Final Comparison

Compare again

``````def fibs(): yield 1; yield 1; yield from map(add, fibs(), tail(fibs()))
``````

``````fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
``````

It's practically the same code! (Yes, the one-line version is hideous Python, I just did that so it would be more comparable with the Haskell version.)

I showed it to one of my friends, who was so impressed that he said "I have no idea what that Python code does".

Next time you get asked Fibonacci as an interview question, consider using this version, and let me know what happens!

## Update!!!!!!

As was pointed out in the comments, one can use `itertools.tee` to split a generator into multiple (efficient) copies. This means that the following slight modification:

``````def fibs():
print("a new fibs")
yield 1
yield 1
fibs1, fibs2 = tee(fibs())