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)

Your code actually looks reasonable (bloated, but not the naive version with two recursive calls per call). How large of a number are we talking here? Are you running into the default recursion limit of 1000? — TigerhawkT3, Apr 29 '16 at 22:02
You're using O(n) stack space here. This would only be O(1) space if Python had tail call elimination. (Actually, it wouldn't be O(1) space anyway, because the assumption that integers take constant space breaks down almost immediately, but that problem is baked into the problem definition. You can't really fix that one.) — user2357112, Apr 29 '16 at 22:05
@JakeBurkhead unless there is a way to write it in a bottom-up fashion without using recursion, then yes recursion is a requirement — donut juice, Apr 29 '16 at 22:08
The standard iterative solution fits your requirements, then. — user2357112, Apr 29 '16 at 22:09
@user2357112 but that isn't bottom-up, iterative is top-down — donut juice, Apr 29 '16 at 22:09
I was under the impression that recalculating each fib(n) down to fib(0) is considered top-down. — OneCricketeer, Apr 29 '16 at 22:11
`fib_in_place(100)` produces an immediate result of 354224848179261915075 on my machine. What happens on your machine? — TigerhawkT3, Apr 29 '16 at 22:11
@donutjuice just convert your recursive calls into the equivalent loop. most always there are equivalent recursive and iterative solutions to problems. they are two ways of doing things repeatedly — Jake Burkhead, Apr 29 '16 at 22:12
@TigerhawkT3 it's a limitation set in the assignment I'm working on. the set recursion limit is 100 — donut juice, Apr 29 '16 at 22:12
If you're supposed to use recursion, and you can only have 100 recursive calls, and you want to find the 100th value... that's either perfectly fine or impossible, depending on off-by-one errors. — TigerhawkT3, Apr 29 '16 at 22:15
This is not O(1) space - it's O(N) - the stack is also taking up some space. — zmbq, Apr 29 '16 at 22:19

score 7 · Answer 1 · answered Apr 29 '16 at 22:22

7

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

answered Apr 29 '16 at 22:22

zmbq

36,789
13
91
160

This is pretty neat. Couldn't really think of an iterative version but this is similar to one of the other answers given. I wish I could give you both the "accepted answer"! – donut juice Apr 29 '16 at 22:25

score 5 · Accepted Answer · edited May 23 '17 at 10:34

5

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

edited May 23 '17 at 10:34

Community

1
1

answered Apr 29 '16 at 22:05

Russia Must Remove Putin

337,988
84
391
326

I'm familiar with this implementation, I want to write it in a bottom-up fashion but not accumulate my answers in a list. Is there a way to do that? – donut juice Apr 29 '16 at 22:07
1

Fun note: the iterative Fibonacci code is the first thing you see when you go to the [official Python home page](http://www.python.org). – TigerhawkT3 Apr 29 '16 at 22:12
When trying your generator version it returns "". Do I need an import or something? – donut juice Apr 29 '16 at 22:19
That *is* fun. @donutjuice You're trading off space for time, whether you store the data in stack frames with recursion or whether you use a cache - only the cache is not as limited nor as expensive in space as a stack is. I don't really know what you mean by bottom-up. I'll demonstrate usage with another function. – Russia Must Remove Putin Apr 29 '16 at 22:20

Prune · Answer 3 · 2016-09-30T03:12:15.710

3

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.

edited Sep 30 '16 at 03:12

answered Apr 30 '16 at 00:22

Prune

75,308
14
55
76

1

Should actually be `f = (phi_1**n - phi_2**n) / math.sqrt(5)`. – Roman Levin Sep 29 '16 at 14:05

score 0 · Answer 4 · answered Apr 29 '16 at 22:49

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.)

bottom up fibonacci in python using O(1) space

4 Answers4

Linked