---
title: "Recursion without mystery — Erkan Malcok"
description: "Understand recursion through base cases, recursive steps and smaller subproblems, with Python examples that show how recursive calls fit together."
date: "2026-09-01"
updated: "2026-09-07"
canonical: "https://erkanmalcok.com/articles/recursion-without-mystery/"
kind: "Article"
series: "algorithms"
tags:
  - "Computer science"
  - "Algorithms"
---

# Recursion without mystery — Erkan Malcok

Base case, recursive step, and when to trust the smaller problem.

Recursion makes beginners nervous for good reason. A function appears to call
itself, the stack grows, and it is easy to lose track of what is happening.

The subject is not magic. Recursion is a way of defining a problem **in terms of
a smaller version of the same problem**, with a clear stopping point. Once those
two pieces are visible, many recursive programs become readable.

## What you will learn

By the end of this article, you should be able to:

- identify the base case and recursive step;
- check that each call moves towards the base case;
- trace a small recursive function without losing track of the result; and
- decide when recursion is clearer than iteration.

## The central idea

Informally:

1. **Base case** — the smallest problem you can answer directly.
2. **Recursive step** — reduce the problem, call the same function on the smaller
   version, and combine the result.

If the base case is correct and each recursive step moves strictly toward that
base case, the computation terminates.

That is the whole contract. Everything else is notation.

When reading or writing a recursive function, ask two questions:

| Question | Purpose |
| --- | --- |
| What is the smallest input I can answer without recursion? | Defines the base case |
| How do I make the input smaller in a safe, repeatable way? | Defines progress toward the base case |

If you cannot answer both, the function is not ready to implement.

## A worked example

The classic introductory example is the factorial of a non-negative integer `n`,
written `n!`:

```
0! = 1
n! = n × (n − 1)!   for n > 0
```

The base case is `0!`. The recursive step multiplies `n` by the factorial of a
smaller value.

```python
def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)
```

Trace `factorial(4)` by hand:

```
factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1 * factorial(0)
= 4 * 3 * 2 * 1 * 1
= 24
```

Each call waits for a smaller call to finish. The base case `factorial(0)` stops
the chain.

Use this reading order:

1. **Find the base case first.** What input ends the recursion?
2. **Check progress.** Does every recursive call use a strictly smaller or
   simpler input?
3. **Trust the recursive call.** Assume the smaller problem is solved correctly,
   then verify the combining step.
4. **Test small inputs.** `0`, `1`, and one non-trivial case often expose missing
   base cases or wrong progress.

Step three is the habit that unlocks recursion. You do not need to unfold the
entire stack in your head. You need to believe that `factorial(n - 1)` returns
the right value, then check that multiplying by `n` is correct.

The same reading habit helps with graph algorithms such as
[Bellman–Ford](/articles/bellman-ford-algorithm/), where repeated relaxation
steps build a correct result from smaller subproblems on shorter paths.

## A common misconception

You do not need to hold the entire call stack in your head before you can
understand a recursive function. That approach often makes recursion feel more
mysterious than it is.

Instead, assume the recursive call correctly solves the smaller problem. Then
check two things: the input really is smaller, and the current call combines the
smaller result correctly. A short trace remains useful for testing that model,
but it is evidence rather than the whole explanation.

## Try it yourself

Write a recursive function `sum_to(n)` that returns the sum of the integers from
`1` to a non-negative integer `n`. Before revealing the answer, state the base
case and explain how the recursive call moves towards it.



### Answer

The base case is `n == 0`, whose sum is `0`. Every other call reduces `n` by
one, so repeated calls eventually reach that base case.

```python
def sum_to(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0
    return n + sum_to(n - 1)
```

For `sum_to(4)`, the calls produce `4 + 3 + 2 + 1 + 0`, which is `10`.



## Use it in practice

Recursion is a natural match when:

- the data structure is recursive (lists, trees);
- the definition of the problem is recursive (factorial, tree traversal);
- a brute-force loop would obscure the structure you are exploiting.

It is a weaker default when:

- a simple loop is clearer and equally correct;
- depth could grow large enough to risk stack overflow;
- tail-call optimisation is not available and performance matters at scale.

For teaching, recursion is still worth learning because it trains you to decompose
problems — a skill that transfers to induction, proof, and dynamic programming.

Watch for these patterns in pupil work:

- **Missing base case** — infinite recursion until stack overflow.
- **Wrong base case** — stops, but on the wrong answer.
- **No progress** — recursive call does not move toward the base case.
- **Duplicated work** — naive Fibonacci recomputes the same values repeatedly
  (a good lead-in to memoisation or iteration).

Debugging recursive code uses the same habits as any other program: reproduce a
small failing input, trace the calls, and name what you expected at each step.

If recursion still feels opaque, practise with tiny functions before large ones:

- sum a list recursively;
- reverse a string;
- traverse a nested list;
- implement binary search on a sorted array.

In each case, write the base case in plain English before writing Python.

Recursion is not an excuse for unclear code. It is a compact way to express
structure — when the structure is real.

## Related reading

- [Bellman–Ford algorithm](/articles/bellman-ford-algorithm/) shows how repeated
  local updates build a correct result across longer paths.
- [Debugging as a teachable habit](/articles/debugging-as-a-teachable-habit/)
  develops the small-input tracing habit used to inspect recursive calls.