Fibonacci case study

How to efficiently calculate Fibonacci numbers in Python.
Python Academy
Author

Bartosz Wróblewski

Published

October 12, 2025

In this post, we will explore different ways to calculate Fibonacci numbers in Python. We will start with a naive recursive approach, and then move to more efficient methods.

Naive Recursive Approach

The Fibonacci sequence is defined by the recurrence relation: \(F_n = F_{n-1} + F_{n-2}\) with seed values \(F_0=0\) and \(F_1=1\).

A naive implementation of this in Python is a direct translation of the mathematical formula:

def fibonacci_recursive(n: int) -> int:
    """Calculate the nth Fibonacci number using a recursive approach."""
    if n < 0:
        raise ValueError("Fibonacci is not defined for negative numbers.")
    if n < 2:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

This approach is very intuitive, but it is also very slow. For n=40, it already takes a noticeable amount of time to compute. The reason for this is that the function calls itself twice for each n, leading to an exponential growth of the call stack.

from time import perf_counter

start = perf_counter()
fibonacci_recursive(40)
end = perf_counter()

print(end - start)
9.671717332996195

Visualizing the Call Stack

To better understand the problem, let’s visualize the call stack. We can create a “talkative” version of our function that logs every call.

from rich.console import Console
from rich.tree import Tree


def fibonacci_recursive_talkative(n: int) -> int:
    """Calculate the nth Fibonacci number using a recursive approach."""
    tree = Tree(f"fibonacci_recursive_talkative({n})")

    def worker(n: int, tree: Tree) -> int:
        """Calculate the nth Fibonacci number using a recursive approach."""
        node = tree.add(f"fibonacci_recursive({n}) called")
        if n < 0:
            raise ValueError("Fibonacci is not defined for negative numbers.")
        if n < 2:
            return n
        return worker(n - 1, node) + worker(n - 2, node)

    result = worker(n, tree)
    Console().print(tree)
    return result

For n=6, the call tree looks like this:

fibonacci_recursive_talkative(6)
fibonacci_recursive_talkative(6)
└── fibonacci_recursive(6) called
    ├── fibonacci_recursive(5) called
    │   ├── fibonacci_recursive(4) called
    │   │   ├── fibonacci_recursive(3) called
    │   │   │   ├── fibonacci_recursive(2) called
    │   │   │   │   ├── fibonacci_recursive(1) called
    │   │   │   │   └── fibonacci_recursive(0) called
    │   │   │   └── fibonacci_recursive(1) called
    │   │   └── fibonacci_recursive(2) called
    │   │       ├── fibonacci_recursive(1) called
    │   │       └── fibonacci_recursive(0) called
    │   └── fibonacci_recursive(3) called
    │       ├── fibonacci_recursive(2) called
    │       │   ├── fibonacci_recursive(1) called
    │       │   └── fibonacci_recursive(0) called
    │       └── fibonacci_recursive(1) called
    └── fibonacci_recursive(4) called
        ├── fibonacci_recursive(3) called
        │   ├── fibonacci_recursive(2) called
        │   │   ├── fibonacci_recursive(1) called
        │   │   └── fibonacci_recursive(0) called
        │   └── fibonacci_recursive(1) called
        └── fibonacci_recursive(2) called
            ├── fibonacci_recursive(1) called
            └── fibonacci_recursive(0) called

8

As you can see, many values are calculated multiple times. For example, fibonacci_recursive(4) is calculated twice, fibonacci_recursive(3) is calculated three times, and so on. This is the reason for the inefficiency.

Memoization

We can improve the performance by storing the results of the function calls in a cache (a dictionary). This technique is called memoization.

__CACHE: dict[int, int] = {}

def fibonacci_recursive_cached(n: int) -> int:
    """Calculate the nth Fibonacci number using recursion with memoization."""
    if n < 0:
        raise ValueError("Fibonacci is not defined for negative numbers.")
    if n < 2:
        return n

    if n in __CACHE:
        return __CACHE[n]
    __CACHE[n] = fibonacci_recursive_cached(n - 1) + fibonacci_recursive_cached(n - 2)

    return __CACHE[n]

This version is much faster. However, it will fail for large n (e.g., n=8_000) because of Python’s recursion depth limit.

try:
    fibonacci_recursive_cached(8_000)
except RecursionError as e:
    print(e)
maximum recursion depth exceeded

Decorators for Caching

A more elegant way to implement memoization is by using a decorator. A decorator is a function that takes another function and extends its behavior without explicitly modifying it. Python’s functools module provides a built-in decorator lru_cache that does exactly what we need.

from functools import cache


@cache
def fibonacci_recursive_cached_decorator(n: int) -> int:
    """Calculate the nth Fibonacci number using recursion with memoization."""
    if n < 0:
        raise ValueError("Fibonacci is not defined for negative numbers.")
    if n < 2:
        return n
    return fibonacci_recursive_cached_decorator(
        n - 1
    ) + fibonacci_recursive_cached_decorator(n - 2)

This is the most concise and Pythonic way to write a cached recursive Fibonacci function.

Iterative Approach

Another way to solve the problem is to use an iterative approach. This is equivalent to tail recursion optimization.

def fibonacci_iterative(n: int) -> int:
    """Calculate the nth Fibonacci number using an iterative approach."""
    if n < 0:
        raise ValueError("Fibonacci is not defined for negative numbers.")
    if n < 2:
        return n

    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

This is the most efficient way (we’ll see)to calculate Fibonacci numbers in Python. It has a linear time complexity and constant space complexity.

Note

Download the whole code here.

Back to top