bottom up fibonacci in python using O(1) space

Question

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
        else:
            return fibo(f1, f2+f1, i -1)
    return fibo(0, 1, n)

Answer 1

Why use iteration at all?

def fib(n):
    phi_1 = (math.sqrt(5) + 1) / 2
    phi_2 = (math.sqrt(5) - 1) / 2
    f = (phi_1**n - phi_2**n) / math.sqrt(5)
    return round(f)

The algebraic result is exact; the round operation is only to allow for digital representation inaccuracy.

Answer 2

Tail-recursive definitions are easily turned into iterative definitions. If necessary, flip the condition so that the tail-recursive call is in the 'if' branch.

def fibo(f2, f1, i):
    if i > 0:
        return fibo(f1, f2+f1, i -1)
    else:
        return f2

Then turn 'if' into 'while', replace return with unpacking assignment of the new arguments, and (optionally) drop 'else'.

def fibo(f2, f1, i):
    while i > 0:
        f2, f1, i = f1, f2+f1, i -1
    return f2

With iteration, you do not need the nested definition.

def fib_efficient(n):
    if n < 0:
        raise ValueError('fib argument n cannot be negative')
    new, old = 0, 1
    while n:
        new, old = old, old+new
        n -= 1
    return new

Local names 'new' and 'old' refer to Fibonacci's use of biological reproduction to motivate the sequence. However, the story works better with yeast cells instead of rabbits. Old, mature yeast cells reproduce by budding off new, immature cells. (The original source of the function in India appears to be Virahanka counting the number a ways to make a Sanskrit poetic line with n beats from an ordered sequence of 1- and 2-beat syllables.)

Answer 3

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)

usage:

>>> 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):
        next(fib_gen)
    return next(fib_gen)

and usage

>>> get_fib(10)
55

Answer 4

Using recursion this way means you're using O(N) space, not O(1) - the O(N) is in the stack.

Why use recursion at all?

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b

    return a