PHASE 5Beginner ~28 min· topic 8 of 10

Topic 5.8

Recursion

In one line

A recursive function solves a problem by calling itself on a smaller version of the same problem, until it reaches a base case it can answer directly. Python allows it, but caps the depth (about 1000 calls by default) and has no tail-call optimisation, so deep problems are usually written as loops.

Think of it like this

Russian nesting dolls. To find the smallest doll, you open the doll in your hand and look inside. If there is another doll, you do the same thing again. When you open one and find nothing inside, you are done. "Open the doll, and repeat on what's inside" is recursion: the same instruction applied to a smaller piece, with a clear place to stop.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Recursion: A function solving a problem by calling itself on a smaller part of it.
Base case: The smallest version of the problem, answered directly without another call.
Recursive case: The part that reduces the problem and calls the function again.
Call stack: The pile of unfinished function calls. Each call adds a frame; returning removes it.
Frame: The record of one call: its parameters, local variables and where to resume.
RecursionError: The error Python raises when the call stack gets deeper than the recursion limit.
Memoisation: Saving results already computed so they can be reused instead of recomputed.
Tail call: A call that is the very last action of a function. CPython does not optimise it.

Step by step

01Base case and recursive case

factorial(n) means n * (n-1) * ... * 1, with factorial(0) defined as 1. The same rule is true at every size: factorial(n) = n * factorial(n - 1). That gives a one-line recursive function.

main.pywhole filepython

def factorial(n):
    if n == 0:                 # base case: stop here
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem


print(factorial(5))   # 120
print(factorial(0))   # 1

02Watching the stack grow and shrink

The trace below prints one line when each call starts and one when it returns, indented by depth. Read it as a story: calls go down to the base case, then answers come back up.

main.pywhole filepython

def fact_trace(n, depth=0):
    pad = "  " * depth
    print(f"{pad}fact_trace({n}) called")
    if n == 0:
        print(f"{pad}base case: return 1")
        return 1
    answer = n * fact_trace(n - 1, depth + 1)
    print(f"{pad}fact_trace({n}) returns {answer}")
    return answer


fact_trace(3)

Watching the stack grow and shrinkdiagram

Rendering diagram…

03No base case: RecursionError

If the function never reaches a base case, the stack grows until Python stops it. The limit is a safety net, not a bug in Python. To keep the output short, the example lowers the limit to 60 and catches the error. (import sys loads a toolbox that comes with Python; Topic 6.1 teaches import. try and except catch an error so the program can print it instead of stopping; Topic 7.1 teaches them.)

Lowering the limit is for experiments only. Always restore it. Raising the limit to a huge number does not make deep recursion safe: the process can still crash from running out of memory.

main.pywhole filepython

import sys

sys.setrecursionlimit(60)


def forever(n):
    return forever(n + 1)    # never stops


try:
    forever(0)
except RecursionError as error:
    print(type(error).__name__ + ":", error)

04Recursion versus a loop

Anything recursive can be written as a loop, and in Python the loop is usually better for plain repetition: it is faster, uses no stack, and has no depth limit. Recursion shines when the data is nested or when you need to try several choices at each step.

main.pywhole filepython

def total_loop(n):
    result = 0
    for i in range(1, n + 1):
        result += i
    return result


print(total_loop(100))    # 5050

05Repeated work and memoisation

fib(n) = fib(n - 1) + fib(n - 2) is a recursive definition, but each call spawns two more, and the same values are recomputed many times. A dictionary that remembers answers cuts the 1973 calls for fib(15) to 29, and makes fib(80) instant.

main.pywhole filepython

memo = {}


def fib_fast(n):
    if n in memo:
        return memo[n]
    if n < 2:
        result = n
    else:
        result = fib_fast(n - 1) + fib_fast(n - 2)
    memo[n] = result
    return result

Repeated work and memoisationdiagram

Rendering diagram…

06A checklist for writing recursion

1) Write the base case first. 2) Check that every recursive call is on a strictly smaller input. 3) Trust the call to solve the smaller problem and use its answer. 4) Test the base case and one step above it. 5) If the depth could pass about 1000, use a loop or an explicit stack.

Try it yourself

1
Trace another number
Call fact_trace(4) and count how many lines of output you expect before you run it. Notice that the indentation is the depth of the stack.
2
Break the base case
Change if n == 0: to if n == -1: in factorial and call factorial(3). The base case is now unreachable. Read the RecursionError that follows (lower the limit first with sys.setrecursionlimit(60) to keep it short).
3
Write countdown
Write countdown(n) that prints n, n-1, ... 1 and then Liftoff! using recursion. Then write it again with a while loop and compare.

Code & diagrams

Factorial and a call trace New tab

Read the trace from top to bottom: the calls go down to 0, then each returns upward.

Expected output

120
1
fact_trace(3) called
  fact_trace(2) called
    fact_trace(1) called
      fact_trace(0) called
      base case: return 1
    fact_trace(1) returns 1
  fact_trace(2) returns 2
fact_trace(3) returns 6

RecursionError, caught and short New tab

The limit is lowered to 60 only to keep the output small, then restored in finally. (`finally` runs its lines whether or not an error happened; Topic 7.1 teaches try, except and finally. `import sys` loads a toolbox that comes with Python; Topic 6.1.)

Expected output

default limit: 1000
RecursionError: maximum recursion depth exceeded
limit restored: 1000

Counting calls: slow, memoised, loop New tab

The same answer, 610, with 1973 calls versus 29. The memoised version also handles fib(80).

Expected output

610 with 1973 calls
610 with 29 calls
23416728348467685
5050

A realistic case: walking nested config New tab

Nested data is where recursion earns its place: a dict or list may hold more dicts and lists, to any depth. The base case is a plain value. The recursion depth follows the nesting depth, which is small for real data. (`max(..., default=0)` returns 0 instead of raising an error when the list is empty.)

Expected output

name                         'api'
database.host                'db.local'
database.port                5432
database.options.ssl         True
database.options.pool[0]     5
database.options.pool[1]     10
features[0]                  'search'
features[1].beta[0]          'chat'
features[1].beta[1]          'voice'
nesting depth: 4

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

A function with no base case

Write a countdown that never checks for the end. (The limit is lowered to 60 to keep the traceback short; with the default limit the message is the same but the output is longer.)

main.pywhole filepython

import sys

sys.setrecursionlimit(60)


def countdown(n):
    return countdown(n - 1)  # no base case


countdown(3)

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 10, in <module>

countdown(3)

~~~~~~~~~^^^

File "main.py", line 7, in countdown

return countdown(n - 1) # no base case

File "main.py", line 7, in countdown

return countdown(n - 1) # no base case

File "main.py", line 7, in countdown

return countdown(n - 1) # no base case

[Previous line repeated 50 more times]

RecursionError: maximum recursion depth exceeded

Myth vs fact

Myth

Recursion is faster than a loop.

Fact

In Python it is usually slower, because each call builds a frame. Recursion is a way to express some problems clearly, not a speed trick.

Myth

Raising the recursion limit fixes RecursionError.

Fact

It only postpones it, and a very high limit can crash the interpreter by exhausting memory. Convert deep recursion to a loop or an explicit stack.

Myth

Python optimises tail recursion.

Fact

It does not. A tail-recursive function still adds a frame per call.

Myth

A recursive function must have the loop-like shape of factorial.

Fact

Recursion also handles trees and nested data, where the function calls itself once per child.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Each Python call allocates a frame object; since Python 3.11 these are created cheaply and kept in a per-thread stack, and since Python 3.12 the recursion limit counts Python-level calls only. Still, depth is bounded by the limit, and pure-Python recursion costs far more than a loop. The limit counts all frames on the stack, including the ones your program was already using, so a function that starts at depth 40 gets about 960 more. Recursion that passes through C code, such as repr or json.dumps on a deeply nested structure, has its own separate C-level limit, and raising setrecursionlimit too high can crash the interpreter with a segmentation fault (stack overflow) instead of a clean RecursionError.
▸
Mutual recursion (two functions calling each other) and indirect recursion obey the same rules. Parsers and tree walkers often use it.
▸
functools.cache (Python 3.9) and functools.lru_cache memoise a function with one decorator line and keep results across calls. Arguments must be hashable (Topic 4.5), and the cache holds memory until cleared. functools is Topic 9.5 and decorators are Topic 9.6.
▸
To avoid the recursion limit for tree or graph walks, keep your own stack (a list) and loop with while stack:. This is how many production tree-walkers and the DSA course's iterative solutions work.

Remember this

1
A recursive function is one that calls itself. Every correct one has two parts. The base case is the smallest version that the function answers directly, without calling itself (factorial(0) is 1). The recursive case reduces the problem and calls itself on the smaller version (n * factorial(n - 1)). Each call must move closer to the base case, or it never stops.
2
Python keeps track of the calls on a call stack: a pile of frames, one per call that has started and not finished. When factorial(3) calls factorial(2), the first call is paused and its frame stays on the pile. The calls pile up until the base case answers; then they finish one by one in reverse order, each using the answer from the one above it.
3
The pile has a height limit. Python allows about 1000 nested calls by default (sys.getrecursionlimit()), and a call that goes deeper raises **RecursionError**. This protects Python from running out of memory. The most common cause is a missing or unreachable base case. Another cause is a problem that is deeper than the limit.
4
Python does not optimise tail calls (a call that is the last thing a function does). Languages such as Scheme turn those into loops; CPython does not, partly because tracebacks would lose frames. So a recursive function that would run a million times in another language must be written as a loop in Python.
5
Recursion fits problems that are naturally nested or self-similar: trees and folders inside folders, nested JSON, splitting a list in halves, trying all choices (backtracking, covered in the DSA course). For simple counting or summing, a for loop is shorter, faster and has no depth limit. Choose recursion when it makes the idea clearer, not because it looks clever.
6
Plain recursion can repeat the same work. A naive Fibonacci calls fib(n - 1) and fib(n - 2), and each of those repeats the same subproblems, so the number of calls explodes (1973 calls for fib(15)). Remembering answers already computed, called memoisation, makes it fast: with a dictionary the same call count falls to 29. Python even has a ready-made version in functools (cache, Python 3.9), which you'll meet with decorators in Phase 9. This is also the first step towards dynamic programming (see the DSA course at /dsa).

Explain it without notes

What are the base case and the recursive case? What goes wrong if either is missing?

Describe what the call stack looks like for factorial(3).

Why does Python raise RecursionError, and what are your options?

How does memoisation speed up Fibonacci?

When should you choose a loop over recursion in Python?

Practice

Write a recursive power(base, exponent) for whole-number exponents of 0 or more, where power(2, 0) is 1. Print power(2, 10).

Write a recursive sum_list(items) that returns the sum of a list. The base case is the empty list. Print sum_list([3, 4, 5]).

Write a recursive flatten(items) that turns a list nested to any depth, such as [1, [2, [3, 4]], 5], into one flat list [1, 2, 3, 4, 5]. Test it on [] and on [[], [[]]] too. Then say why count_down(5000), a recursive function that makes the list [5000, 4999, ..., 1] one call per number, would fail with the default limit while flatten on real data would not.

Trade-offs

↔
Clarity versus limits. Recursion mirrors nested problems and reads like the definition, but it is bound by the recursion limit and is slower than a loop for simple repetition.
↔
Memoisation: speed versus memory. A cache turns exponential time into linear, but stores every result. For very large input ranges it can use a lot of memory; bound it with lru_cache(maxsize=...).

Done when you can

Done when you can identify the base case and the recursive case in a recursive function.
Done when you can draw or trace the call stack for a small input.
Done when you can explain RecursionError and fix a missing base case.
Done when you can rewrite a simple recursive function as a loop.
Done when you can explain how a dictionary memo speeds up fib.

Command Palette

Words you'll meet

Step by step

01Base case and recursive case

02Watching the stack grow and shrink

03No base case: RecursionError

04Recursion versus a loop

05Repeated work and memoisation

06A checklist for writing recursion

Try it yourself

Trace another number

Break the base case

Write countdown

Code & diagrams

Break it on purpose

A function with no base case

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can