donut juice donut juice - 2 years ago 114
Python Question

bottom up fibonacci in python using O(1) space

I want to write a bottom up fibonacci using O(1) space. My problem is python's recursion stack is limiting me from testing large numbers. Could someone provide an alternate or optimization to what I have? This is my code:

def fib_in_place(n):
def fibo(f2, f1, i):
if i < 1:
return f2
return fibo(f1, f2+f1, i -1)
return fibo(0, 1, n)

Answer Source

You can memoize the Fibonacci function for efficiency, but if you require a recursive function, it's still going to take at least O(n):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

This is from my answer on the main Fibonacci in Python question: How to write the Fibonacci Sequence in Python

If you're allowed to use iteration instead of recursion, you should do this:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)


>>> list(zip(range(10), fib()))
[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21), (9, 34)]

If you just want to get the nth number:

def get_fib(n):
    fib_gen = fib()
    for _ in range(n):
    return next(fib_gen)

and usage

>>> get_fib(10)
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download