Updated for Python 3.12+ · Intermediate · 10 lessons

Recursion & Memoisation
in Python

Learn to think recursively, understand the call stack, avoid the classic pitfalls, and speed up recursive functions with memoisation and functools.lru_cache. Every example is runnable in your browser with line-by-line explanations.

Intermediate base case call stack factorial fibonacci memoisation lru_cache
Back to Home Full Curriculum
factorial.py
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(10))
$ python factorial.py
120
3628800

📖 Introduction — Thinking Recursively

Solving a problem by solving a smaller version of itself

Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. It's a natural way to express algorithms that have a self-similar structure: traversing a tree, computing a factorial, or parsing a nested data structure. The idea is simple: if you know how to solve the small case, and you know how to break a big case into a slightly smaller one, you can solve everything.

But recursion has a reputation. Beginners find it confusing because the flow of execution — which line runs next, which function call is "active" — is harder to follow than a simple loop. The source of that confusion is almost always the call stack: the behind-the-scenes structure Python uses to track which function calls are currently in progress. Once you understand the call stack, recursion becomes dramatically less mysterious.

The core mental model

A recursive function has two kinds of cases: base cases that don't recurse (they return a value directly) and recursive cases that call the function again with a smaller input. The key invariant is that every recursive call must move closer to a base case — otherwise you get infinite recursion. When a recursive call returns, its value is used to compute the result of the caller, which returns to its caller, and so on back up the stack.

🔄 Recursion vs. iteration — when to use which

✅ Use recursion when…

The problem has a naturally recursive structure: trees, nested lists, divide-and-conquer algorithms (merge sort, quicksort), or backtracking (mazes, sudoku). The code is often much shorter and clearer.

⚠️ Use iteration when…

The problem is a simple loop, or the input could be very deep. Python has a recursion limit (default 1000), and each call adds a stack frame. For deep data, a loop is often safer.

📋 What this lesson covers

  • ✓The anatomy of a recursive function: base case + recursive case
  • ✓How the call stack works, step by step, with a visual trace
  • ✓Classic examples: factorial, Fibonacci, tree traversal
  • ✓Why naive Fibonacci is slow — and how memoisation fixes it
  • ✓functools.lru_cache, Python's built-in memoisation decorator
  • ✓Tail recursion, and why Python doesn't optimise it
  • ✓Common pitfalls: infinite recursion, missing base cases, stack overflow

🔬 The Anatomy of a Recursive Function

Every recursive function has exactly two kinds of cases

No matter how complex a recursive function looks, it always breaks down into the same two parts. Understanding this structure is the first step toward writing your own.

Base case — a condition that returns a value without calling the function again. This is what stops the recursion. Every recursive function must have at least one base case, and every chain of recursive calls must eventually reach one.

Recursive case — a condition that calls the function again with a smaller or simpler input. The result of that call is combined with the current input to produce the answer.

📝 Example — a simple countdown

def countdown(n):
    if n <= 0:
        print("Done!")
        return
    print(n)
    countdown(n - 1)

countdown(3)
Lines 2–4 — the base case: when n reaches 0, print "Done!" and return without recursing. This is what stops the chain.
Lines 5–6 — the recursive case: print the current n, then call countdown(n - 1) with a smaller value. Each call gets closer to the base case.
Line 8 — the initial call starts the chain: 3 → 2 → 1 → 0 → Done!

⚠️ What happens if you forget the base case?

def infinite(n):
    print(n)
    infinite(n + 1)

try:
    infinite(0)
except RecursionError as e:
    print(f"RecursionError: {e}")
Lines 1–3 — there's no base case. Every call increases n, moving further from any stopping point.
Line 5 — after about 1000 calls, Python raises RecursionError: maximum recursion depth exceeded. This is Python's safety net against infinite recursion.
💡 The default recursion limit is 1000. You can check it with sys.getrecursionlimit() and change it with sys.setrecursionlimit() — but changing it is usually a sign that you should rewrite the algorithm iteratively.

🗂️ The Call Stack — How Python Tracks Recursive Calls

Once you see the stack, recursion stops being confusing

Every time a function is called, Python pushes a stack frame onto the call stack. The frame holds the function's local variables and the exact point in the code where execution should resume when the function returns. When a function returns, its frame is popped, and execution continues in the caller's frame at the point just after the call. In recursion, the same function's frame appears many times — one for each active call.

📊 Visual trace — factorial(4)

Let's trace the calls to factorial(4), where factorial(n) = n * factorial(n - 1) and factorial(1) = 1.

factorial(4) ← frame pushed │ n = 4 │ needs: 4 * factorial(3) ↓ factorial(3) ← frame pushed │ n = 3 │ needs: 3 * factorial(2) ↓ factorial(2) ← frame pushed │ n = 2 │ needs: 2 * factorial(1) ↓ factorial(1) ← frame pushed │ n = 1 │ base case: returns 1 ↑ returns 2 * 1 = 2 ← frame for factorial(2) popped ↑ returns 3 * 2 = 6 ← frame for factorial(3) popped ↑ returns 4 * 6 = 24 ← frame for factorial(4) popped
The descent — each call adds a frame and defers computation: 4 * …, 3 * …, 2 * …. Nothing is multiplied yet — each frame is waiting for the call below it to return.
The base case — factorial(1) hits the base case and returns 1 immediately. This is the turning point.
The ascent — as each frame receives the return value from the frame below it, it performs its multiplication and returns: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24.
The key insight — recursion has two phases: descent (calling) and ascent (returning). The actual work happens on the ascent.

🔍 Inspecting the stack depth

You can see the recursion depth in action by printing the value of a counter that increases with each call.

def trace_depth(n, depth=0):
    print("  " * depth + f"n={n}, depth={depth}")
    if n == 0:
        print("  " * depth + "base case reached")
        return
    trace_depth(n - 1, depth + 1)

trace_depth(3)
Line 2 — indentation visualises the stack depth. Each level is indented more.
Line 3–5 — the base case prints a marker and returns.
Line 6 — the recursive call passes depth + 1 so the next frame knows its level.
Output — you'll see n=3 at depth 0, n=2 at depth 1, n=1 at depth 2, n=0 at depth 3, then "base case reached". This is the descent in action.

⚠️ Stack overflow — when recursion goes too deep

Each frame consumes memory. If a recursive function descends too far — because of a missing base case, or because the input is genuinely very deep — Python raises RecursionError before the program runs out of memory.

import sys

print(f"Default recursion limit: {sys.getrecursionlimit()}")

def deep(n):
    if n == 0:
        return 0
    return 1 + deep(n - 1)

print(f"deep(100): {deep(100)}")

try:
    deep(2000)
except RecursionError as e:
    print(f"RecursionError: {e}")
Line 3 — the default limit is 1000 frames.
Line 11 — deep(100) uses 101 frames (one per level plus the original) — well under the limit.
Line 13 — deep(2000) exceeds the limit and raises RecursionError: maximum recursion depth exceeded.
The fix — rewrite the function iteratively, or increase the limit with sys.setrecursionlimit(5000) — but be cautious: very deep stacks can crash the interpreter.

🧮 Classic Example 1 — Factorial

The canonical first recursion example

The factorial of a non-negative integer n, written n!, is the product of all positive integers from 1 to n. It's defined recursively: 0! = 1 (base case) and n! = n × (n−1)! (recursive case). This definition maps directly to a recursive function.

📝 Recursive factorial with detailed output

def factorial(n):
    print(f"  calling factorial({n})")
    if n <= 1:
        print(f"  base case: factorial({n}) = 1")
        return 1
    result = n * factorial(n - 1)
    print(f"  returning factorial({n}) = {result}")
    return result

print(f"factorial(5) = {factorial(5)}")
Line 2 — every call prints its argument, so you can trace the descent.
Lines 3–5 — base case: factorial(1) returns 1 directly. This is the turning point.
Line 6 — the recursive case: compute n * factorial(n - 1). The multiplication can't happen until the recursive call returns.
Line 7 — this line runs on the ascent, after the recursive call has returned. It prints the value being returned to the caller.
Output — you'll see the descent (calling 5, 4, 3, 2, 1), the base case, then the ascent (returning 1, 2, 6, 24, 120).

🔁 Iterative version — often simpler for linear problems

Factorial doesn't need recursion. A simple loop works just as well and uses constant stack space.

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))
print(factorial_iterative(10))
Line 2 — start with 1. For n = 0 or 1, the loop doesn't run and returns 1.
Lines 3–4 — multiply result by each integer from 2 to n. This is exactly what the recursive version does, but iteratively.
Why it's better here — no stack frames, no recursion limit. For n = 5000, the iterative version works; the recursive one raises RecursionError.
💡 Rule of thumb: if a problem can be expressed as a simple loop, use a loop. Reserve recursion for problems that are genuinely recursive — where the structure of the data or the algorithm is self-similar (trees, nested structures, divide-and-conquer).

📈 Classic Example 2 — Fibonacci (and Why Naive Recursion Is Slow)

The example that motivates memoisation

The Fibonacci sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n−1) + F(n−2) for n ≥ 2. It's a perfect candidate for recursion — the definition literally calls for it. But the naive recursive implementation is exponentially slow, and understanding why is the key to understanding memoisation.

📝 Naive recursive Fibonacci

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

import time

start = time.time()
print(fib_naive(30))
print(f"Took {time.time() - start:.3f} seconds")
Lines 2–3 — base cases: F(0) = 0, F(1) = 1.
Line 4 — recursive case: two recursive calls per invocation. This is what makes it slow.
Line 8 — timing fib_naive(30). It takes roughly a second on a typical machine — and fib_naive(35) would take over 10 seconds.

🌳 Why it's slow — the recursion tree

Here's the call tree for fib_naive(5). Notice how many times the same subproblem is computed.

fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ │ ├── fib(1) │ │ │ └── fib(0) │ │ └── fib(1) │ └── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(3) ├── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(1) fib(2) is computed 3 times. fib(3) is computed 2 times. fib(4) is computed 1 time.
The problem — fib(2) is recomputed three times. For larger n, the number of redundant calls grows exponentially.
The complexity — naive Fibonacci has O(2^n) time complexity. fib(30) makes about 1.6 million calls; fib(40) makes over 300 million.
The fix — remember the result of each subproblem the first time you compute it. Then each subproblem is computed only once. That's memoisation.

📊 Comparing the three approaches

ApproachTime complexitySpace complexityWhen to use
Naive recursionO(2^n)O(n)Almost never — too slow for n > 30
Memoised recursionO(n)O(n)When the recursive structure is natural and you need speed
Iterative (bottom-up)O(n)O(1)When you can compute values in order from the start
💡 Memoisation trades space for time. It stores the result of every subproblem so it never has to be recomputed. The iterative version does the same thing with an even smaller footprint — but memoisation generalises to problems where the dependency structure is more complex than a simple linear sequence.

🌳 Classic Example 3 — Tree Traversal

Where recursion is genuinely the right tool

Trees are the canonical recursive data structure: a tree is either empty or a root node with subtrees. Traversing a tree — visiting every node in a specific order — is naturally recursive because the operation on a tree is defined in terms of the same operation on its subtrees. Iterative tree traversal is possible (with an explicit stack), but the recursive version is dramatically clearer.

📝 Example — a simple binary tree and its traversals

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value, end=" ")
    inorder(node.right)

def preorder(node):
    if node is None:
        return
    print(node.value, end=" ")
    preorder(node.left)
    preorder(node.right)

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value, end=" ")

root = Node(1,
    left=Node(2, left=Node(4), right=Node(5)),
    right=Node(3, left=Node(6), right=Node(7))
)

print("In-order:  ", end=""); inorder(root); print()
print("Pre-order: ", end=""); preorder(root); print()
print("Post-order:", end=""); postorder(root); print()
Lines 1–5 — a Node holds a value and optional left/right children. A leaf has both children as None.
Lines 7–11 — in-order traversal: left subtree, then current node, then right subtree. For a binary search tree, this visits nodes in sorted order.
Lines 13–17 — pre-order traversal: current node, then left, then right. Used for copying a tree or serialising it.
Lines 19–23 — post-order traversal: left, then right, then current node. Used for deleting a tree or evaluating expression trees.
Line 25–29 — build a tree with 7 nodes. The root is 1, with two subtrees of 3 nodes each.
Output — in-order visits 4 2 5 1 6 3 7; pre-order visits 1 2 4 5 3 6 7; post-order visits 4 5 2 6 7 3 1.
💡 The base case for all three traversals is the same: if node is None: return. The only difference between the three traversals is the order of the three recursive steps. This is why recursion is so natural for trees — the recursive calls mirror the structure of the data.

🔁 Iterative in-order traversal — for comparison

The iterative version is possible, but it requires an explicit stack and is harder to get right. This is the classic argument for using recursion for tree problems.

def inorder_iterative(root):
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.value, end=" ")
        current = current.right

inorder_iterative(root)
print()
Line 2 — an explicit stack replaces the call stack.
Lines 4–7 — push all left children until hitting None. This mimics the recursive "go all the way left" step.
Line 8 — pop the deepest-left node and visit it.
Line 10 — move to its right subtree and repeat.
Why recursion wins here — the iterative version is 9 lines of fiddly stack management. The recursive version is 4 lines and directly mirrors the definition of in-order traversal.

⚡ Memoisation — Remembering Results to Avoid Recomputation

The single most important optimisation for recursive functions

Memoisation is a technique where you cache the result of a function call, keyed by its arguments. The next time the function is called with the same arguments, you return the cached result instead of recomputing it. For recursive functions with overlapping subproblems — like Fibonacci — this reduces exponential time to linear time.

📝 Manual memoisation with a dictionary

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    memo[n] = result
    return result

import time
start = time.time()
print(fib_memo(100))
print(f"Took {time.time() - start:.6f} seconds")
Lines 2–3 — memo is the cache. The first call creates it; recursive calls pass the same dictionary down. This is the classic mutable-default workaround (using None and creating the dict inside) to avoid shared state across calls.
Lines 4–5 — the cache check: if n is already in memo, return the stored result immediately. This is what makes it fast.
Lines 6–7 — the base case, as before.
Line 8 — the recursive case. Both recursive calls share the same memo dictionary, so a result computed by one call is visible to the other.
Line 9 — the cache write: store the result before returning it, so future calls can find it.
Output — fib_memo(100) returns almost instantly (in microseconds), compared to the naive version which would take billions of years.
💡 The manual version is educational but not idiomatic. In real Python code, you should use functools.lru_cache — which is cleaner, faster, and less error-prone.

📊 Before and after — memoisation in numbers

nNaive callsMemoised callsSpeedup
1017719~9×
2021,89139~560×
302,692,53759~45,000×
40331,160,28179~4,200,000×

The memoised version makes exactly 2n − 1 calls because each subproblem is computed once. The naive version recomputes the same subproblems exponentially many times.

🚀 functools.lru_cache — Memoisation in One Line

Python's built-in memoisation decorator

The functools module includes lru_cache, a decorator that memoises any function automatically. "LRU" stands for "Least Recently Used" — when the cache reaches its maximum size, the least recently used entry is evicted. By default, the cache is unbounded (on Python 3.9+), but you can set maxsize to control memory usage.

📝 The modern Fibonacci — one decorator line

from functools import lru_cache
import time

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

start = time.time()
print(fib(100))
print(f"Took {time.time() - start:.6f} seconds")
print(f"Cache info: {fib.cache_info()}")
Line 1 — import the decorator.
Line 4 — @lru_cache(maxsize=None) wraps fib in a memoising wrapper. maxsize=None means unlimited cache size.
Lines 5–8 — the function body is unchanged. The decorator handles all the caching.
Line 11 — fib(100) returns in microseconds. Internally, the decorator stores the result of each fib(n) the first time it's computed.
Line 13 — fib.cache_info() returns a named tuple with hits, misses, maxsize, and currsize. This is useful for monitoring cache effectiveness.
💡 lru_cache requires that all arguments be hashable — which means no lists or dicts as arguments. For those cases, you'll need to convert to tuples, or implement a custom memoisation scheme.

🔍 Understanding the cache — a trace

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    print(f"computing fib({n})")
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(5))
print("---")
print(fib(5))
print(f"Cache info: {fib.cache_info()}")
Line 6 — prints every time the function actually computes a value (cache miss).
First fib(5) — you'll see computing fib(5), computing fib(4), computing fib(3), computing fib(2), computing fib(1), computing fib(0) — in that order. After computing each value, it's stored.
Second fib(5) — no computing lines at all. All values are in the cache — all hits.
Cache info — CacheInfo(hits=10, misses=6, maxsize=None, currsize=6). The first call had 6 misses (values 0–5), and the second call had 10 hits (every recursive call hit the cache).

💾 Bounded cache — controlling memory

For very large or unbounded computations, you may want to limit the cache size. When the cache is full, the least recently used entry is evicted.

from functools import lru_cache

@lru_cache(maxsize=128)
def compute_expensive(n):
    return n ** 2

for i in range(200):
    compute_expensive(i)

print(f"Cache info: {compute_expensive.cache_info()}")
Line 3 — maxsize=128 limits the cache to 128 entries.
Lines 6–7 — we call the function 200 times with different arguments. Only 128 results fit in the cache.
Line 9 — currsize will be 128, and maxsize will be 128. The first 72 entries (least recently used) were evicted.
When to use a bounded cache — when the function is called with a wide range of arguments and you can't afford to hold all results in memory. A reasonable default is often maxsize=128 or maxsize=1024.
💡 In Python 3.9+, you can also use functools.cache — it's identical to lru_cache(maxsize=None) and is slightly faster because it skips some of the LRU bookkeeping. Use cache when you know the cache should be unbounded.

⚠️ When lru_cache doesn't work

❌ Unhashable arguments

@lru_cache
def f(items):
    return sum(items)
Lists and dicts can't be cache keys.

✅ Convert to a tuple

@lru_cache
def f(items_tuple):
    return sum(items_tuple)
Callers pass tuple(items).

Mutable arguments can't be hashed, and caching requires hashing. The standard workaround is to convert to an immutable form — tuple instead of list, frozenset instead of set, or a sorted tuple of items instead of a dict.

➡️ Tail Recursion — and Why Python Doesn't Optimise It

A theoretical optimisation that Python chooses not to apply

A tail-recursive function is one where the recursive call is the very last operation — nothing is done with its result except returning it. In languages that support tail-call optimisation (TCO), this means the current stack frame can be replaced by the new one, so tail recursion uses constant stack space. Python does not implement TCO, so tail-recursive functions still grow the stack. Knowing this helps you avoid a common mistake.

📝 Non-tail vs. tail recursion — factorial

def factorial_non_tail(n):
    if n <= 1:
        return 1
    return n * factorial_non_tail(n - 1)

def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, accumulator * n)

print(factorial_non_tail(5))
print(factorial_tail(5))
Lines 1–4 — the standard version. The recursive call is not the last operation: its result is multiplied by n before returning. The multiplication is deferred until the recursive call returns.
Lines 6–9 — the tail-recursive version. It passes an accumulator that accumulates the result so far. The recursive call is the last operation — its result is returned directly.
Why it matters — in a language with TCO, the tail version would use constant stack space. In Python, both versions use O(n) stack space, because Python does not perform TCO.
💡 In Python, tail recursion is an interesting academic exercise but not a practical optimisation. If you need constant-stack recursion, rewrite the function iteratively. The tail-recursive version is often a good intermediate step — it's usually easy to convert to a loop.

🔄 From tail recursion to iteration

The tail-recursive factorial converts directly to a loop by replacing the accumulator parameter with a local variable and the recursive call with an iteration step.

def factorial_iterative(n):
    accumulator = 1
    while n > 1:
        accumulator *= n
        n -= 1
    return accumulator

print(factorial_iterative(5))
Line 2 — the accumulator becomes a local variable.
Lines 3–5 — the loop replaces the recursive call. Each iteration multiplies the accumulator and decrements n, exactly as the tail-recursive version does.
Line 6 — return the accumulated result.
The benefit — this version uses constant stack space and has no recursion limit. It will work for n = 10000, where the recursive version would fail with RecursionError.

⚠️ Common Pitfalls and How to Avoid Them

The mistakes almost everyone makes when learning recursion

❌ Pitfall 1 — Missing or unreachable base case

If no base case is ever reached, the recursion continues until Python's recursion limit is exhausted. This is the most common cause of RecursionError.

def countdown_buggy(n):
    print(n)
    countdown_buggy(n - 1)

try:
    countdown_buggy(5)
except RecursionError as e:
    print(f"RecursionError: {e}")
Lines 1–3 — there's no base case, so every call recurses with a smaller value forever.
The error — after about 1000 calls, Python raises RecursionError: maximum recursion depth exceeded.
The fix — add if n <= 0: return before the recursive call.

❌ Pitfall 2 — Recursive call doesn't move toward the base case

If the input to the recursive call is the same as or larger than the current input, the base case will never be reached — even if it exists.

def stuck(n):
    if n == 0:
        return "done"
    return stuck(n)

try:
    stuck(5)
except RecursionError as e:
    print(f"RecursionError: {e}")
Line 4 — stuck(n) calls with the same n, so n never reaches 0. The base case exists but is unreachable.
The fix — each recursive call must make progress toward the base case. Typically this means passing n - 1 instead of n.

❌ Pitfall 3 — Forgetting to combine the recursive result

A common mistake is to call the function recursively but forget to use its return value.

def sum_list_buggy(items):
    if not items:
        return 0
    sum_list_buggy(items[1:])

print(sum_list_buggy([1, 2, 3]))
Line 4 — the recursive call is made, but its result is discarded. The function returns None, not the sum.
The fix — use the recursive result: return items[0] + sum_list_buggy(items[1:]).
Why it happens — it's easy to think of the recursive call as "doing the work" without realising that the caller has to combine the returned value.

❌ Pitfall 4 — Using recursion for deep or unbounded input

Python's default recursion limit is 1000. For data that could be deeper — a long linked list, a deeply nested JSON document, a large tree — recursive solutions will hit the limit.

import sys

print(f"Recursion limit: {sys.getrecursionlimit()}")

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(500))

try:
    sum_to(2000)
except RecursionError as e:
    print(f"RecursionError: {e}")
Line 3 — the limit is 1000. sum_to(500) uses 501 frames — under the limit.
Line 12 — sum_to(2000) exceeds the limit and raises RecursionError.
The fix — for problems that can be expressed iteratively, prefer iteration. For genuinely recursive data, either increase the recursion limit carefully (with sys.setrecursionlimit()) or use an explicit stack.
⚠️ Raising the recursion limit is not a general solution. Very deep stacks can cause a segmentation fault or crash the interpreter. If you find yourself needing a limit above a few thousand, the algorithm is usually better expressed iteratively.

❌ Pitfall 5 — Exponential recomputation (the Fibonacci problem)

Naive recursion on problems with overlapping subproblems recomputes the same values exponentially many times. The fix is memoisation — either manual or with lru_cache.

from functools import lru_cache

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

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

import time

start = time.time()
fib_slow(25)
slow_time = time.time() - start

start = time.time()
fib_fast(25)
fast_time = time.time() - start

print(f"Slow: {slow_time:.6f}s, Fast: {fast_time:.6f}s")
print(f"Speedup: {slow_time / fast_time:.0f}×")
Lines 3–6 — naive Fibonacci. Exponential time.
Lines 8–12 — memoised Fibonacci with lru_cache. Linear time.
Lines 16–22 — timing both. For n = 25, the naive version is typically 100–1000× slower.
The lesson — if a recursive function has overlapping subproblems, memoisation is not optional. It's the difference between a working program and one that never finishes.

📋 Quick-Reference Cheat Sheet

Recursion and memoisation at a glance — bookmark this page

✅ The anatomy of a recursive function

Base case ← returns a value directly, no recursive call Recursive case ← calls the function with a smaller input │ └── every recursive path must reach a base case

🔄 Recursion vs. memoisation

TechniqueWhat it doesWhen to use
RecursionSolves a problem by solving smaller instances of the same problemThe data or algorithm is naturally recursive
Manual memoisationCaches results in a dict you pass aroundWhen you need fine control over the cache
lru_cacheCaches results automatically via a decoratorAlmost always — it's simpler and faster
IterationSolves the problem with a loopWhen the problem is linear and depth could be large

🔑 The five rules of recursion

Every recursive function needs a base case. Without one, you get infinite recursion and RecursionError.

Every recursive call must move toward the base case. If the input doesn't get smaller or simpler, the base case is unreachable.

Use the result of the recursive call. A recursive call that discards its return value is almost always a bug.

Beware of overlapping subproblems. If the same subproblem is computed more than once, memoise it — manually or with lru_cache.

Prefer iteration for linear problems. Python's recursion limit is 1000. For deep data, a loop is safer and often just as clear.

What to remember from this lesson

1. A recursive function has a base case and a recursive case. Every recursive path must reach the base case.
2. The call stack tracks active calls. Descent = calling; ascent = returning. The actual work happens on the ascent.
3. Naive Fibonacci is O(2n) because it recomputes subproblems. Memoisation makes it O(n).
4. functools.lru_cache is the idiomatic way to memoise in Python. It requires hashable arguments.
5. Python does not implement tail-call optimisation. Tail recursion still grows the stack. Use iteration for deep recursion.

Back to Home Full Curriculum