Fibonacci Series in Python: Iterative, Recursive, and Generator Approaches

The Fibonacci sequence starts with 0 and 1. Every subsequent number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

It shows up in technical interviews, algorithm courses, and occasionally in nature. Python gives you at least three clean ways to generate it — each with different trade-offs worth understanding.

Approach 1: Iterative Loop

The simplest method. Build the sequence by keeping track of just the two previous values and appending each new one.

def fibonacci_iterative(n):
    """Return a list containing the first n Fibonacci numbers."""
    if n <= 0:
        return []
    if n == 1:
        return [0]

    sequence = [0, 1]
    for _ in range(2, n):
        # Each new value is the sum of the previous two
        sequence.append(sequence[-1] + sequence[-2])
    return sequence

print(fibonacci_iterative(10))
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Time complexity: O(n). Space complexity: O(n) for the stored list. This is the version to reach for in production code.

Approach 2: Recursive Function

The mathematical definition of Fibonacci maps naturally to a recursive function: fib(n) = fib(n-1) + fib(n-2).

def fibonacci_recursive(n):
    """Return the nth Fibonacci number (0-indexed)."""
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Print the first 10 terms
for i in range(10):
    print(fibonacci_recursive(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

The problem: this recomputes the same values over and over. fib(30) makes millions of calls. Fix it with memoisation using functools.lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    """Memoised recursive Fibonacci — O(n) time, O(n) space."""
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

print(fibonacci_memo(50))
# Output: 12586269025  (instant, even for large n)

With the cache, each subproblem is solved once. Time and space complexity both drop to O(n).

Approach 3: Generator

When you only need one Fibonacci number at a time — or want to iterate through them without storing the full list — a generator is the right tool. It uses constant memory regardless of how far you go.

def fibonacci_generator():
    """Infinite Fibonacci generator — yields one value at a time."""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Take only the first 10 values using itertools.islice
from itertools import islice

gen = fibonacci_generator()
first_ten = list(islice(gen, 10))
print(first_ten)
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Time complexity: O(1) per value yielded. Space: O(1) — only two variables kept in memory at any time.

Comparing the Three Approaches

Common Interview Variations

Find the nth Fibonacci number (not the full list): use the generator with next() called n times, or the memoised recursive version.

Check if a number is Fibonacci: a positive integer x is a Fibonacci number if and only if 5x² + 4 or 5x² - 4 is a perfect square.

import math

def is_fibonacci(x):
    """Return True if x is a Fibonacci number."""
    def is_perfect_square(n):
        root = int(math.isqrt(n))
        return root * root == n

    return is_perfect_square(5 * x * x + 4) or is_perfect_square(5 * x * x - 4)

print(is_fibonacci(13))   # True
print(is_fibonacci(14))   # False

The iterative loop is the right default answer in an interview unless you are specifically asked about recursion or generators.