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

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download