Discussion on: Recursion Algorithm Practice: Fibonacci Sequence Generator

All the best for the interview!

Another interesting approach using iteration is making the function into a generator which can be used as part of for loops, list comprehensions, etc

def gen_fib():
    a,b = 1,1
    yield a
    yield b
    while True:
        a,b = b,a+b
        yield b
g = gen_fib()
# Generate the first 200,000 Fibonacci numbers
fibs = [next(g) for _ in range(200000)]

I am generally wary of writing code using pure recursion in Python as it can easily blow the stack due to recursion limit. For example if we try to solve using recursion as:

def fib(n):
    if n <= 1:
        return 1
    return fib(n-2)+fib(n-1)

This takes exponential time because it recalculates fib(n-2) for fib(n-1).

If we try to make it linear time using functools.lru_cache which will cache the previous calls at cost of O(n) memory, this still gives maximum recursion depth exceeded in comparison error for fib(200000).

@lru_cache(maxsize=None)
def fib_3(n):
    if n <= 1:
        return 1
    return fib_3(n-2) + fib_3(n-1)

if Tail call optimization was supported in Python, the following recursive variant will be "optimized" to iterative version:

def fib_tail(n):
  def fib_helper(a, b, n):
    return fib_helper(b, a + b, n-1) if n > 0 else a
  return fib_helper(0, 1, n)

But due to no TCO, it still results in same maximum recursion depth exceeded in comparison for fib_tail(200000)