donut juice - 1 year ago 81

Python 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

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
```

Source (Stackoverflow)