Recursion: functions that call themselves

How a function solves a task by calling itself on a smaller version of it: the base case and the recursive step, the call stack and `RecursionError`, factorial, Fibonacci, digit sums, recursive binary search, nested lists and folder trees — and when a loop or `lru_cache` is the better choice.

  • Intermediate
  • 22 min
  • 12 questions
  • Lesson 11 of 66

In this lesson you will learn

  • Write a recursive function with a correct base case and a recursive step that moves towards it
  • Explain how the call stack grows and shrinks and why a RecursionError happens
  • Solve classic tasks recursively: factorial, Fibonacci, digit sums and binary search
  • Process nested data (lists, folder trees) and choose between recursion, a loop and lru_cache

A folder holds files and other folders, and those folders hold more files and folders. How do you count all the files if you do not know how deep the nesting goes? A for loop has to know in advance what it walks over. But this task has a nice property: counting the files in a subfolder is the same task, only smaller. A function that solves a task by calling itself on a smaller part of it is called recursive. In the lesson «Functions» you learned to define and call functions; now a function will call itself.

RecursionDefinition

A way of solving a problem in which a function calls itself with a smaller or simpler input. Every recursive function has two parts: a base case, answered directly without a new call, and a recursive step, which makes the problem smaller and calls the function again.

Base case and recursive step

The simplest example is a countdown. countdown(3) prints 3 and hands the rest of the work — counting down from 2 — to countdown(2). When n reaches 0, the function prints Start! and stops: that is the base case. Factorial is built the same way: to find 5! we need 4!, for 4! we need 3!, and so on down to 1! = 1.

n! = n · (n − 1)!0! = 1! = 1

Where

n
a natural number
n!
the product 1 · 2 · … · n

The rule repeats the same operation on a smaller number (the recursive step) and gives a value we know without calculating (the base case).

Python
def countdown(n):
    if n == 0:               # base case
        print('Start!')
        return
    print(n)
    countdown(n - 1)         # recursive step


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


countdown(3)
print(factorial(5), factorial(10))
Expected output
3
2
1
Start!
120 3628800
countdown returns nothing, it only prints; factorial passes its result back to the caller with return.

Worked example: unfolding factorial(4)

Problem

Without running the code, compute factorial(4) step by step and say how many calls are made.

Show solutionHide solution

Solution

factorial(4) = 4 · factorial(3)
factorial(3) = 3 · factorial(2)
factorial(2) = 2 · factorial(1)
factorial(1) = 1 — base case, no new call.
Now the results travel back: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.
There are 4 calls: one for each n = 4, 3, 2, 1.

Sign up free to keep reading

The rest of the lesson, the quiz and your notes open with an Educora account. Signing up takes a minute, and your progress is saved on all your devices.

The call stack and RecursionError

How can one function be running several times at once? Each call gets its own frame: a small area of memory with its own parameters and local variables. Frames are kept on the call stack: a new call goes on top, and when a call finishes with return, its frame is removed and the result goes to the frame below. While factorial(1) runs, factorial(4), factorial(3) and factorial(2) are all waiting on the stack, each with its own n.

Call stackDefinition

The list of function calls that have started but not finished yet, ordered last in, first out. The top frame is the one running now; the others are waiting for its result.

↑ a new call goes on topreturnsfactorial(1)base case: returns 1factorial(2)waiting for 2 · factorial(1)factorial(3)waiting for 3 · factorial(2)print(factorial(3))the program waits for the result126
Calls make the stack grow upwards; each return removes the top frame.
Python
def factorial(n, depth=0):
    pad = '    ' * depth
    print(f'{pad}factorial({n}) called')
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f'{pad}factorial({n}) returns {result}')
    return result


print('answer:', factorial(4))
Expected output
factorial(4) called
    factorial(3) called
        factorial(2) called
            factorial(1) called
            factorial(1) returns 1
        factorial(2) returns 2
    factorial(3) returns 6
factorial(4) returns 24
answer: 24
The indentation shows the depth of the stack. Calls go down to the base case, and the results come back in the opposite order.

The stack is not endless. By default CPython allows about 1000 nested calls (sys.getrecursionlimit() shows the limit). If the base case is missing or never reached, the calls never stop, the limit is hit and Python stops the program with RecursionError: maximum recursion depth exceeded. Below, broken has no base case at all, and also_broken has one, but with an odd n the step n − 2 jumps over 0:

Python
def broken(n):
    return n * broken(n - 1)          # no base case


def also_broken(n):
    if n == 0:
        return 0
    return n + also_broken(n - 2)     # an odd n jumps over 0


for func, arg in ((broken, 5), (also_broken, 6), (also_broken, 7)):
    try:
        print(func.__name__, arg, '->', func(arg))
    except RecursionError:
        print(func.__name__, arg, '-> RecursionError')
Expected output
broken 5 -> RecursionError
also_broken 6 -> 12
also_broken 7 -> RecursionError
also_broken(6) = 6 + 4 + 2 + 0 = 12. With 7 the sequence is 7, 5, 3, 1, −1, … and never meets 0. A safer base case would be if n <= 0.

`return` forgotten

def digit_sum(n):
    if n < 10:
        return n
    n % 10 + digit_sum(n // 10)

correct

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)
Without return, digit_sum(25) returns None, and for 2026 the program even crashes: one level up Python has to compute 2 + None and raises TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'.

Classic tasks: digit sums, Fibonacci, binary search

Many definitions in mathematics are recursive already. The digit sum of a number is its last digit (n % 10) plus the digit sum of the number without that digit (n // 10); a one-digit number is its own digit sum. Fibonacci numbers are defined through the two previous members of the sequence.

S(n) = n % 10 + S(n // 10)S(n) = n, if n < 10

Where

S(n)
the digit sum of n
n % 10
the remainder after division by 10 — the last digit
n // 10
integer division — drops the last digit

S(2026) = 6 + S(202) = 6 + 2 + S(20) = 6 + 2 + 0 + S(2) = 10.

F(n) = F(n − 1) + F(n − 2)F(0) = 0F(1) = 1

Where

F(n)
the n-th Fibonacci number

Two base cases are needed because the step looks two members back.

Python
def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)


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


print(digit_sum(2026), digit_sum(4096), digit_sum(987654321))
print([fib(n) for n in range(12)])
Expected output
10 19 45
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
4096 → 6 + 9 + 0 + 4 = 19; 987654321 → 9 + 8 + … + 1 = 45.

Worked examples: predict the result

Problem

1) digit_sum(507); 2) fib(7); 3) how many times is digit_sum called for a 6-digit number?

Show solutionHide solution

Solution

1) 7 + digit_sum(50) = 7 + 0 + digit_sum(5) = 7 + 0 + 5 = 12.
2) F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, F(7) = 13.
3) Each call drops one digit until a single digit is left: 6 calls for a 6-digit number (k digits — k calls).

The Fibonacci function is short but very slow. Every call makes two more calls, and the same values are computed again and again: fib(5) computes fib(3) twice and fib(2) three times. The number of calls grows almost as fast as the Fibonacci numbers themselves:

calls(n) = 2 · F(n + 1) − 1

Where

calls(n)
the number of calls made by the naive fib(n)

For n = 20: F(21) = 10946, so 2 · 10946 − 1 = 21891 calls — exactly what the program below counts.

Python
from functools import lru_cache

calls = 0


def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)


for n in (10, 20, 25):
    calls = 0
    value = fib(n)
    print(f'fib({n}) = {value}: {calls} calls')


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


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


print(fib_cached(90), fib_loop(90), fib_cached.cache_info().misses)
Expected output
fib(10) = 55: 177 calls
fib(20) = 6765: 21891 calls
fib(25) = 75025: 242785 calls
2880067194370816120 2880067194370816120 91
lru_cache remembers every result, so fib_cached(90) needs only 91 real calculations (misses) — one for each n from 0 to 90. The loop version keeps just the last two numbers and needs no stack at all. How lru_cache works is explained in the lesson «Decorators and closures».

Binary search finds a value in a sorted list by halving the range at every step — each step solves the same task on half the data. We pass the borders lo and hi instead of slicing the list, because every slice would copy the elements.

  1. Empty range

    If lo > hi, the value is not there: return -1 (base case).

  2. Middle element

    mid = (lo + hi) // 2; if items[mid] == target, return mid (base case).

  3. Right half

    If items[mid] < target, search the range [mid + 1..hi].

  4. Left half

    Otherwise search the range [lo..mid − 1].

Python
def binary_search(items, target, lo=0, hi=None):
    if hi is None:
        hi = len(items) - 1
    if lo > hi:                          # base case: nothing left
        return -1
    mid = (lo + hi) // 2
    print(f'  range [{lo}..{hi}], items[{mid}] = {items[mid]}')
    if items[mid] == target:             # base case: found
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, hi)
    return binary_search(items, target, lo, mid - 1)


scores = [12, 25, 31, 47, 58, 63, 77, 84, 90, 96]
print('77 at index', binary_search(scores, 77))
print('50 at index', binary_search(scores, 50))
Expected output
  range [0..9], items[4] = 58
  range [5..9], items[7] = 84
  range [5..6], items[5] = 63
  range [6..6], items[6] = 77
77 at index 6
  range [0..9], items[4] = 58
  range [0..3], items[1] = 25
  range [2..3], items[2] = 31
  range [3..3], items[3] = 47
50 at index -1
10 elements need at most 4 steps: the range shrinks 10 → 5 → 2 → 1. A million elements need only about 20 steps, because 2²⁰ ≈ 10⁶.

Interactive

Loading simulation…
Watch binary search halve the range step by step.

Recursive data: nested lists and folder trees

Recursion feels most natural when the data itself is recursive: lists inside lists, folders inside folders, comments with replies that have replies. The shape of the function follows the shape of the data: an ordinary element is the base case, and for a nested element the function calls itself again.

Python
def total(data):
    result = 0
    for item in data:
        if isinstance(item, list):
            result += total(item)        # a smaller list of the same kind
        else:
            result += item
    return result


def depth(data):
    if not isinstance(data, list):
        return 0
    return 1 + max((depth(x) for x in data), default=0)


expenses = [120, [30, 45, [5, 5]], 60, [[10], 20]]
print(total(expenses), depth(expenses))
print(total([]), depth([]), depth(7))
Expected output
295 3
0 1 0
total adds every number at any depth: 120 + 30 + 45 + 5 + 5 + 60 + 10 + 20 = 295. depth counts the levels of brackets; default=0 takes care of an empty list.

A folder tree can be described with nested dictionaries: a key is a name, a number is a file size in KB, and a dictionary is a subfolder. The function prints the tree and returns its size, and every subfolder is handled by the same function one level deeper:

Python
tree = {
    'school': {
        'math': {'algebra.pdf': 320, 'geometry.pdf': 410},
        'photos': {'trip': {'baku.jpg': 2048, 'quba.jpg': 1730}, 'class.png': 960},
        'plan.txt': 12,
    }
}


def show(folder, indent=0):
    size = 0
    for name, content in folder.items():
        if isinstance(content, dict):          # a folder: recurse
            print('    ' * indent + name + '/')
            size += show(content, indent + 1)
        else:                                  # a file: base case
            print('    ' * indent + f'{name} ({content} KB)')
            size += content
    return size


print('Total:', show(tree), 'KB')
Expected output
school/
    math/
        algebra.pdf (320 KB)
        geometry.pdf (410 KB)
    photos/
        trip/
            baku.jpg (2048 KB)
            quba.jpg (1730 KB)
        class.png (960 KB)
    plan.txt (12 KB)
Total: 5480 KB

Now a real disk. In the pathlib module Path.iterdir() lists the contents of a folder, and is_dir() tells a folder from a file. The program first builds a small project folder (recursively as well), then walks through it and reports the number of files and bytes in every folder:

Python
from pathlib import Path


def make(folder, spec):
    for name, content in spec.items():
        path = folder / name
        if isinstance(content, dict):
            path.mkdir()
            make(path, content)
        else:
            path.write_text('x' * content)


def report(folder, indent=0):
    files, size = 0, 0
    for path in sorted(folder.iterdir()):
        if path.is_dir():
            f, s = report(path, indent + 1)
            print('  ' * indent + f'{path.name}/  files={f}, bytes={s}')
            files, size = files + f, size + s
        else:
            files, size = files + 1, size + path.stat().st_size
    return files, size


root = Path('project')
root.mkdir()
make(root, {'docs': {'a.txt': 120, 'b.txt': 80, 'old': {'c.txt': 300}},
            'src': {'main.py': 450}, 'readme.md': 50})
print(report(root))
print(sum(p.stat().st_size for p in root.rglob('*') if p.is_file()))
Expected output
  old/  files=1, bytes=300
docs/  files=3, bytes=500
src/  files=1, bytes=450
(5, 1000)
1000
A folder’s line is printed after the lines of its subfolders, because its totals are known only once they have been counted. rglob('*') walks the tree for you and gives the same 1000 bytes: in real scripts rglob and os.walk are the ready-made tools, but inside they do exactly this.

Recursion or a loop?

Any recursive function can be rewritten with a loop (with your own stack list if needed), and the other way round. Which one to choose depends on the shape of the task:

SituationBetter choiceWhy
a simple sequence: the sum 1…n, factorial, a countdownloopno stack, no depth limit, usually faster
tree-shaped data: nested lists, folders, JSON, HTMLrecursionthe code follows the shape of the data
divide and conquer: binary search, merge sort, quicksortrecursionthe depth is only about log₂ n
the same subproblems again and again (Fibonacci)recursion + lru_cache, or a loopevery value is computed once
the depth can reach thousands of levelsa loop with an explicit stackno RecursionError
Python
def sum_rec(n):
    return 0 if n == 0 else n + sum_rec(n - 1)


def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


print(sum_rec(100), sum_loop(100))
try:
    print(sum_rec(100_000))
except RecursionError:
    print('sum_rec(100000): RecursionError')
print(sum_loop(100_000))
Expected output
5050 5050
sum_rec(100000): RecursionError
5000050000
Every recursive call adds a frame, so sum_rec(100000) needs 100 000 frames and fails, while the loop needs none. Python does not optimise tail recursion, so rewriting the function in another recursive form does not help either.

Exercise

Write the recursive function power(x, n): xⁿ = x · xⁿ⁻¹ and x⁰ = 1 (n is a whole number ≥ 0). Do not use the ** operator or pow. Keep the three calls of the starter code.

Exercise · Python
def power(x, n):
    # base case: n == 0
    # recursive step: x * power(x, n - 1)
    pass


print(power(2, 10))
print(power(3, 4))
print(power(5, 0))
Expected output
1024
81
1

Exercise

The function count_files(folder) must return the number of files in a nested dictionary: a key whose value is a dictionary is a subfolder, and a key whose value is a number is a file. An empty folder has 0 files.

Exercise · Python
tree = {
    'docs': {'cv.pdf': 120, 'letters': {'a.txt': 4, 'b.txt': 6}},
    'music': {},
    'photo.jpg': 900,
}


def count_files(folder):
    # a dict value is a subfolder, a number is a file
    pass


print(count_files(tree))
print(count_files(tree['docs']))
print(count_files(tree['music']))
Expected output
4
3
0

Remember

  • A recursive function calls itself on a smaller input; it needs a base case and a step that really moves towards it.
  • Every call gets its own frame on the call stack; results come back in the reverse order of the calls.
  • Without a reachable base case the stack overflows: RecursionError (about 1000 levels by default in CPython). A step without return gives None.
  • Recursion suits tree-shaped data and divide-and-conquer tasks: nested lists, folder trees, binary search.
  • Repeated subproblems → functools.lru_cache; simple or very deep sequences → a loop.
Spotted a mistake or something inaccurate in this lesson?

Check yourself

12 questions. Every correct answer earns XP.

Question 1 / 12

Question 1 / 12. What are the two required parts of a recursive function?