MiddleCodeCommonNot answered yet
Compute Fibonacci iteratively and as a generator
Implement two things without exponential recursion.
Requirements:
fib(n)returns the nth Fibonacci number in O(n) time and O(1) space.fib_gen()is an infinite generator yielding0, 1, 1, 2, 3, ...lazily.
def fib(n: int) -> int:
# your code here
def fib_gen():
# your code hereWrite the implementation.
Iterate with a tuple-swap: a, b = 0, 1; for _ in range(n): a, b = b, a + b; return a — O(n) time, O(1) space, no exponential recursion. The generator yields lazily: while True: yield a; a, b = b, a + b. Python ints are arbitrary-precision, so there is no overflow.
- ✗Naive double recursion (exponential time)
- ✗Claiming a full list is O(1) space
- ✗Trusting Binet's float formula to stay exact for large n
- →Why does the tuple-swap
a, b = b, a + bwork in a single step? - →How does the generator version let a caller take just the first k values?
Contents
Task
Implement fib(n) in O(n)/O(1) and an infinite generator fib_gen() without exponential recursion.
Solution
def fib(n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def fib_gen(): # infinite generator
a, b = 0, 1
while True:
yield a
a, b = b, a + bKey points
- The tuple-swap
a, b = b, a + bupdates both values in one step with no temporary. - The iterative version is O(n) time, O(1) space; naive recursion is exponential.
- Python ints are arbitrary-precision, so Fibonacci never overflows.
Contents
