Python · Recursion · Performance

Computing Recurrences in Python

Recursion is not what makes some recurrences slow. Repeated work is. In this post, we compute a simple recurrence in Python, compare loop-based and recursive approaches, and show exactly when memoization matters—and when it barely changes anything.

What a recurrence is

A recurrence has two parts: a rule and a base case. For example:

$$T(n) = T(n-1) + n, \quad T(1)=1$$

This means every new value is the previous value plus n.

Iterative solution

def recurrence(n: int) -> int:
    if n < 1:
        raise ValueError("n must be at least 1")

    total = 1
    for k in range(2, n + 1):
        total += k
    return total

This loop is simple, efficient, and avoids recursion depth issues.

Recursive solution with caching

from functools import cache


@cache
def recurrence_recursive(n: int) -> int:
    if n < 1:
        raise ValueError("n must be at least 1")
    if n == 1:
        return 1
    return recurrence_recursive(n - 1) + n

This version mirrors the math very closely, which makes it helpful for learning.

Important: caching avoids repeated work, but it does not remove Python’s recursion depth limit. Very large inputs can still raise RecursionError. In production code, the iterative version is usually safer.

Why memoization matters

For a recurrence like T(n) = T(n-1) + n, caching is not a huge win because each value depends on only one earlier value. The real benefit appears in branching recurrences such as Fibonacci:

$$F(n)=F(n-1)+F(n-2)$$

from functools import cache

call_count = 0


def fib_no_cache(n: int) -> int:
    global call_count
    call_count += 1
    if n <= 2:
        return 1
    return fib_no_cache(n - 1) + fib_no_cache(n - 2)


@cache
def fib_cached(n: int) -> int:
    if n <= 2:
        return 1
    return fib_cached(n - 1) + fib_cached(n - 2)

Without caching, the same subproblems are solved again and again. With caching, each input is solved once.

Closed form for the example recurrence

Our recurrence expands to:

$$T(n)=1+2+3+\cdots+n = \frac{n(n+1)}{2}$$

def closed_form(n: int) -> int:
    if n < 1:
        raise ValueError("n must be at least 1")
    return n * (n + 1) // 2

That gives the same answer directly, with no loop and no recursion.

When to use each approach

Approach	Best use	Main caution
Iterative	Practical, fast, memory-efficient code	May feel less like the math definition
Recursive + cache	Learning and naturally recursive formulas	Still limited by recursion depth
Closed form	Fast direct computation	Only available when you know or can derive the formula

Raell Dottin's Technical Blog