Recursion explained simply: base cases and recursive calls

Recursion is one of those concepts that, the first time, looks like a magic trick: a function that calls itself and somehow arrives at the result. Then, at some point, something clicks and it becomes a natural tool for describing problems with a nested structure, such as folders inside folders, comments with replies, menus with submenus. Let us see how to think recursively without getting lost.

The idea in two ingredients

A recursive function solves a problem by reducing it to a smaller version of the same problem. Two elements are always needed:

1. the base case: a situation simple enough to solve directly, with no further calls;
2. the recursive step: the way of reducing the problem to a smaller one, moving closer to the base case.

The classic example is the factorial: the factorial of 5 is 5 × 4 × 3 × 2 × 1. But you can also say that the factorial of 5 is 5 multiplied by the factorial of 4.

def factorial(n):
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)   # recursive step

If the base case is missing, or if the recursive step does not move towards it, the function calls itself forever.

What really happens

Every function call takes up space on the call stack, where its parameters and local variables are kept. When factorial(4) is called, the stack grows like this:

factorial(4) waits for 4 * factorial(3)
  factorial(3) waits for 3 * factorial(2)
    factorial(2) waits for 2 * factorial(1)
      factorial(1) returns 1

Then the calls close in reverse order: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24. Visualising the stack this way is the best way to understand a recursive function that does not behave as expected.

The mental trick: trust the call

The most common mistake learners make is trying to follow every call mentally all the way down. With complex problems it is impossible. The correct approach is an act of controlled trust: assume the recursive call on a smaller problem works, and only ask yourself how to use its result.

To calculate the total size of a folder:

from pathlib import Path

def size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size           # base case
    return sum(size(p) for p in path.iterdir())

You do not need to picture all the subfolders: it is enough to know that size returns the correct size of each contained item, and that the folder's size is their sum. The base case, a file, closes the chain.

Where recursion shines

Recursion is particularly suited to structures that contain smaller versions of themselves:

• trees: file systems, HTML documents, organisational structures, comments with nested replies;
• nested data: JSON files with objects inside objects;
• divide-and-conquer algorithms: merge sort, quicksort, binary search;
• exploring possibilities: generating every combination or solving a puzzle by trying and stepping back (backtracking).

In all these cases an iterative version is possible, but it usually requires managing a stack by hand, and is longer and less readable.

The problem of repeated calls

Here is the most naive recursive version of the Fibonacci sequence, where each number is the sum of the two before it:

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

It is elegant but extremely slow: fib(5) calculates fib(3) twice, fib(2) three times, and the number of calls grows exponentially. The solution is memoization, that is, remembering results already calculated:

from functools import lru_cache

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

With just one extra line, each value is calculated once and the complexity becomes linear.

Practical limits

In Python the depth of recursion is limited: beyond a certain threshold, by default around a thousand calls, you get a RecursionError. Python also does not apply the tail-call optimisation found in other languages. For this reason:

Raising the limit with sys.setrecursionlimit is possible, but it is more a temporary remedy than a solution.

In short

• A recursive function always has a base case and a step that moves towards it.
• Every call takes space on the stack: visualising it helps you understand the behaviour.
• Reason by trusting the call on a smaller problem, rather than following every one.
• Recursion is ideal for trees and nested data; memoization avoids repeated calculations.
• In Python depth is limited: for long processing, prefer a loop.