The Fibonacci sequence in python looks something like this

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

But expect stack overflows for even small values of n, e.g., fib(60) will require over 3 trillion function calls. You can use the Fibonacci sequence itself to compute the number of function calls.

I.e., both fib(0) and fib(1) require only one function call,
fib(2) will call fib(1) and fib(0) for a total of 3 function calls,
fib(3) will call fib(2) and fib(1) for a total of 1+3+1=5 function calls,
fib(4) will call fib(3) and fib(2) for a total of 1+5+3=9 function calls,
fib(5) will call fib(4) and fib(2) for a total of 1+9+5=15 function calls, and so on…

In fact, for any n > 1, fib(0) will be called exactly fib(n-2) times and fib(1..n) will be called fib(n-i) times (for every i 1..n). In python you can compute this as follows:

def recursive_fib_counter(n):
    count = fib(n-2)
    for k in range(1,n):
        count += fib(n-k)
    return count

This will produce an interesting series: 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, … which is known as the Leonardo Numbers. Dijkstra wrote about their relationship to the Fibonacci sequence in 1981. And here I thought I was on to something.

Anyway, this is all well and great, but obviously inefficient– a Fibonacci sequence ought to be computed linearly, i.e., O(n) time. And to make this interesting, we can utilize python magic to create a Fibonacci object that behaves like a list.

class Fibonacci(object):
    """lazy loading Fibonacci sequence"""
    def __init__(self):
        self.fib = [0,1]

    def __getitem__(self, n):
        self._fib(n)
        return self.fib[n]

    def __getslice__(self, start, end):
        self._fib(max(start,end,len(self.fib)))
        return self.fib[start:end]

    def __call__(self, n):
        return self.__getitem__(n)

    def _fib(self, n):
        for i in range(len(self.fib), n+1):
            self.fib.insert(i, self.fib[i-1] + self.fib[i-2])
        return self.fib[n]

This way you can create a Fibonacci sequence, access it as a callable function or as a list, including list splicing, behold:

>>> fib = Fibonacci()
>>> fib[5]
5
>>> fib[0:10]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> fib(60)
1548008755920L
>>> from decimal import *
>>> phi = Decimal(fib(9999)) / Decimal(fib(9998))
>>> phi
Decimal('1.618033988749894848204586834')

Best of all it’s extremely fast, in the recursive model fib(9999) would be computationally impossible, even fib(500) would require more than a google of recursive function calls, and fib(9999) would require more than 10²⁰⁹⁰ function calls.

And while the Fibonacci object is iterable, it’s also infinite (like the Fibonacci sequence itself), so it’s best to iterate over a list returned by a splice rather than iterate over the object itself (which again, is computationally infinite), e.g.,

>>> fib = Fibonacci()
>>> for i in fib[0:5]:
	print(i)

0
1
1
2
3
>>> 
>>> ## I'll leave this as an exercise for the reader, go on, it's kind of fun
>>> ##  (you'll probably want to Ctrl-C at some point)
>>> for i in fib:
	print(i)
        ...