# Recursion, Finally

> The mental model that makes recursion stop being scary: a base case, a step toward it, and trust - plus when it blows the stack and how to avoid it.


---

# Recursion, Finally

You have read the definition five times. "A function that calls itself." You nod, you write one, and your brain quietly screams: *if it calls itself, when does it ever stop?* It feels like staring into two mirrors facing each other. That dizziness is normal, and it goes away the moment you have the right mental model instead of a clever phrase.

This guide gives you that model. Recursion is two small parts and one act of trust. Once those click, the trick that looked like magic turns into something you can read, write, and reason about on purpose.

## How to read this

Read the phases in order; each one builds the next. Phase 1 is the model - do not skip it, because everything else rests on it. Type the examples out yourself. Recursion is one of those topics where reading along feels fine and then your fingers freeze on a blank file; the cure is to write the small ones by hand until the shape feels obvious.

## The phases

1. [The mental model: stop, shrink, trust](01-the-mental-model.md) - what recursion actually is and why your brain fights it.
2. [Writing recursion that works](02-writing-recursion-that-works.md) - the everyday patterns and how to build one without losing the thread.
3. [When it breaks: the stack, and when to use a loop instead](03-when-it-breaks.md) - stack overflow, depth limits, and recursion versus iteration in real code.


---

# The mental model: stop, shrink, trust

Here is the thing nobody tells you up front: the reason recursion feels impossible is that you are trying to trace the whole thing in your head. You imagine the function calling itself, which calls itself, which calls itself, and you try to hold all of it at once. Your working memory taps out around three levels deep, and then it feels like falling.

Stop trying to trace it. That is not how anyone reads recursion, including the people who write it fluently. The trick is to think about exactly one call at a time and trust the rest.

## A recursive function is two parts

Every recursive function answers two questions, and that is all:

1. **When do I stop?** This is the **base case** - the smallest input, the one you can answer without thinking, with no further calls.
2. **How do I take one step toward stopping?** This is the **recursive case** - do a little work, then hand a *smaller* version of the problem to yourself.

That is the whole shape. Stop, or shrink and pass it on. Let's make it concrete with the most boring example on earth, counting down:

```python
def countdown(n):
    if n == 0:          # base case: nothing left to count
        print("liftoff")
        return
    print(n)            # do a little work
    countdown(n - 1)    # smaller version of the same problem
```

*What just happened:* `countdown(3)` prints `3`, then calls `countdown(2)`, which prints `2`, then `countdown(1)`, then `countdown(0)` - which hits the base case, prints `liftoff`, and stops. The chain ends because every call gets a *smaller* `n`, and `0` is the floor.

Notice the two parts are both doing real jobs. The base case is the wall that stops the fall. The `n - 1` is the guarantee that you actually move toward that wall. Take away either one and the whole thing breaks - we will see exactly how in phase 3.

## The leap of faith

Here is the move that makes recursion click, and it genuinely feels like cheating the first time.

When you write the recursive call, **assume it already works.**

You do not trace into it. You do not follow it down. You write `countdown(n - 1)` and you *believe* that it correctly counts down from `n - 1`. Your only job is to handle the one step in front of you - print `n` - and to make sure the smaller call is, in fact, smaller.

Think of it like delegating. You are a manager handed a stack of 100 forms. You do not process all 100 yourself. You handle the top form, hand the other 99 to an assistant, and *trust* they will do those correctly. That assistant does the same: handles one, passes 98 down. Nobody holds the whole stack. Each person does one form and trusts the rest.

> The mental shift: stop asking "how does the whole recursion resolve?" Start asking "if the smaller call works, does my one step give the right answer?" If yes, and the base case is correct, the whole thing is correct. That is the entire skill.

## A real example: factorial

`5!` (five factorial) means `5 × 4 × 3 × 2 × 1`. Notice the self-similar shape hiding in it: `5!` is `5 × 4!`. And `4!` is `4 × 3!`. The problem contains a smaller copy of itself - that is the signal that recursion fits.

```python runnable
def factorial(n):
    if n == 0:              # base case: 0! is 1, by definition
        return 1
    return n * factorial(n - 1)   # trust: factorial(n-1) is correct

print(factorial(5))   # 120
```

*What just happened:* `factorial(5)` returns `5 * factorial(4)`. We do not trace into `factorial(4)` - we trust it returns `24`, so `factorial(5)` returns `120`. Each call multiplies its own `n` by the trusted answer of the smaller call, and `factorial(0)` returns `1` to anchor the whole product.

Read that function again with the leap of faith in mind. The line `return n * factorial(n - 1)` says: "my answer is `n` times *the answer to the smaller problem*, which I trust is right." You never have to unfold all five multiplications in your head. You check one step and one base case.

## If you have seen proof by induction, you already know this

This is not a loose analogy - it is the same idea wearing different clothes. In [mathematical induction](/guides/what-a-proof-is) you prove a statement by showing it holds for a base case (`n = 0`), then showing that *if* it holds for `n - 1`, it holds for `n`. That "if it holds for the smaller case" assumption is exactly the leap of faith. Induction proves your recursive function is correct, and writing a recursive function is induction you can run. If one ever made sense to you, the other is the same muscle.

## For builders

When you size up a new problem, the tell for recursion is self-similarity: does solving it involve solving a smaller version of the same problem? Counting down, walking a folder tree, navigating a [tree or linked list](/guides/data-structures-explained) - all self-similar, all natural fits. A flat list of numbers you sum left to right? That is a loop's job. Recognizing the shape is most of the battle; the syntax is the easy part.

```quiz
[
  {
    "q": "What are the two required parts of a recursive function?",
    "choices": ["A loop and a counter", "A base case and a recursive case", "Two function calls", "An input and an output"],
    "answer": 1,
    "explain": "The base case says when to stop; the recursive case does one step and hands a smaller problem to itself."
  },
  {
    "q": "What does 'the leap of faith' mean when writing a recursive call?",
    "choices": ["Hope it eventually stops", "Trace every nested call by hand", "Assume the smaller call already returns the correct answer", "Add a try/except around it"],
    "answer": 2,
    "explain": "You handle only the one step in front of you and trust the smaller call is correct - like delegating the rest of the stack."
  },
  {
    "q": "Why does factorial(5) eventually stop?",
    "choices": ["Python limits multiplication", "Each call passes a smaller n until it reaches the base case n == 0", "The return statement breaks the loop", "It does not stop; it runs forever"],
    "answer": 1,
    "explain": "Every call shrinks n by one, marching toward the base case at 0, which returns without making another call."
  }
]
```

Watch it animated: [recursion](/explainers/Recursion.dc.html)


---

# Writing recursion that works

You have the model. Now the question that actually trips people at the keyboard: when you sit down to *write* one, where do you start, and how do you keep from getting lost? There is a reliable recipe, and once you follow it a few times it stops feeling like a recipe and starts feeling like how you see the problem.

## The recipe: base case first, always

Write the base case before anything else. This is not a style preference - it is what keeps you from writing an infinite loop. Ask: "what is the smallest input I can answer instantly, without recursing?" Write that, return, done.

Then write the recursive case as if the smaller call already works. Three questions, in order:

1. **What is the smallest case?** Answer it directly. (Base case.)
2. **How do I shrink the input by one step?** (The argument to the recursive call.)
3. **Given the trusted smaller answer, how do I build my answer?** (Combine.)

Let's run the recipe on summing a list:

```python runnable
def sum_list(nums):
    if not nums:                    # 1. smallest case: empty list sums to 0
        return 0
    return nums[0] + sum_list(nums[1:])   # 3. first item + trusted sum of the rest

print(sum_list([4, 2, 7, 1]))   # 14
```

*What just happened:* the empty list is the floor, returning `0`. Every other call peels off `nums[0]`, trusts `sum_list(nums[1:])` to sum the remaining items, and adds them. `[4,2,7,1]` becomes `4 + sum([2,7,1])` becomes `4 + (2 + sum([7,1]))` and so on down to the empty list.

That `nums[1:]` is the shrink step - each call gets a strictly shorter list, so the empty list is guaranteed to arrive. **Every recursive case must move toward the base case.** If your "smaller" input is not actually smaller, you have a bug, not a recursion.

## The call stack: where the in-progress work waits

To trust recursion you do not need to trace it, but to *debug* it you should know what is happening underneath. Every time a function calls another (including itself), the computer saves the current call's state - its variables, its place in the code - onto the **call stack**, and starts the new call. When a call returns, its frame is popped off and the call underneath picks up exactly where it paused.

Here is `factorial(3)` as a stack. Calls pile up on the way down, then unwind on the way back up:

```text
call factorial(3)   ->  needs 3 * factorial(2)   [waiting]
  call factorial(2) ->  needs 2 * factorial(1)   [waiting]
    call factorial(1) -> needs 1 * factorial(0)  [waiting]
      call factorial(0) -> base case, returns 1
    factorial(1) resumes: 1 * 1  = 1   returns
  factorial(2) resumes: 2 * 1    = 2   returns
factorial(3) resumes: 3 * 2      = 6   returns
```

*What just happened:* the calls stack up until the base case (`factorial(0)`) returns a real value with no further calls. Then each paused call wakes up, plugs in the answer from the call above it, and returns its own answer downward. The "waiting" frames are why recursion can do work *after* the recursive call returns.

That last point matters. A loop does its work as it goes. Recursion can also do work on the way *back up* - each frame was paused mid-expression (`3 * ___`) and finishes once the inner answer arrives. That unwinding is the recursion's superpower and, as you will see in phase 3, also where it can run out of room.

## Two calls, one function: branching recursion

Recursion really earns its keep when a problem splits into more than one smaller problem. The classic is walking a tree or any nested structure. Here is summing every number in an arbitrarily nested list:

```python runnable
def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):     # a sub-list: trust deep_sum to handle it
            total += deep_sum(x)
        else:
            total += x
    return total

print(deep_sum([1, [2, [3, 4], 5], 6]))   # 21
```

*What just happened:* the base case is implicit - a list with no sub-lists never recurses and the loop returns its plain sum. When the loop hits a sub-list, it trusts `deep_sum` to total that branch however deep it goes. You did not write code for "three levels deep"; you wrote code for "one level, and trust the rest," and it handles any depth.

> Try writing iterative code that sums an *arbitrarily* nested list. You can, but you end up manually managing a stack of your own - which is exactly what recursion was doing for you for free. When the structure is nested or branching, recursion is usually the shorter, clearer code.

## In the wild

This shape is everywhere once you spot it. Walking a directory tree to find files: handle this folder's files, recurse into each subfolder. Rendering nested UI components: render this node, recurse into its children. Parsing JSON: a value might contain objects that contain values. All of them lean on the same move - handle one node, trust the function with the rest. Tree and list structures are covered in [data structures explained](/guides/data-structures-explained), and they are recursion's natural home.

```quiz
[
  {
    "q": "When writing a recursive function, what should you write first?",
    "choices": ["The recursive call", "The base case", "A test", "The combine step"],
    "answer": 1,
    "explain": "Writing the base case first ensures the recursion has a place to stop and keeps you from writing an infinite loop."
  },
  {
    "q": "What does the call stack hold while a recursive call is in progress?",
    "choices": ["Only the final answer", "Nothing; recursion uses no memory", "The paused state of each waiting call, to resume after the inner one returns", "A copy of the whole program"],
    "answer": 2,
    "explain": "Each call's variables and position are saved on the stack, then resumed when the call it is waiting on returns."
  },
  {
    "q": "In sum_list, why is nums[1:] essential?",
    "choices": ["It makes the code faster", "It is the shrink step that moves toward the empty-list base case", "It reverses the list", "It copies the list for safety"],
    "answer": 1,
    "explain": "Each call must get a strictly smaller input; passing the rest of the list guarantees the empty list is eventually reached."
  }
]
```


---

# When it breaks: the stack, and when to use a loop instead

Recursion is elegant until the day it isn't. You run your function and instead of an answer you get an angry wall of red text mentioning a "maximum recursion depth" or a "stack overflow." This phase is the production reality: the two ways recursion fails, how to read the error, and how to decide when a plain loop is the better tool.

## Failure one: no base case (or you never reach it)

The call stack is not infinite. Every paused call takes memory, and that memory is finite. If your recursion never hits its base case, the calls pile up forever until the space runs out and the program dies.

```python
def countdown(n):
    print(n)
    countdown(n - 1)    # forgot the base case!

countdown(3)
```

*What just happened:* this prints `3, 2, 1, 0, -1, -2, ...` and keeps going. There is no `if n == 0: return`, so nothing ever stops the descent. Python eventually raises `RecursionError: maximum recursion depth exceeded`. The fix is not subtle - add the base case back.

The sneakier version of this bug *has* a base case but never reaches it, because the recursive call does not actually shrink toward it:

```python
def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n)        # bug: passes n, not n - 1
```

*What just happened:* the base case exists, but `n` never changes, so `n == 0` is never true for a call that started above zero. Same crash. The lesson: a base case is necessary but not sufficient - **every recursive call must move strictly closer to it.** When you debug a stack overflow, check both: is there a base case, and does each call genuinely get smaller?

## Failure two: correct, but too deep

This one is meaner because the code is *right*. Sometimes a perfectly correct recursion goes deeper than the stack allows. Summing a list one element per call works fine for 100 items and explodes for 100,000:

```python
def sum_list(nums):
    if not nums:
        return 0
    return nums[0] + sum_list(nums[1:])

sum_list(list(range(100_000)))   # RecursionError
```

*What just happened:* this is the exact correct function from phase 2, but it needs one stack frame per element. Many language runtimes cap recursion depth (Python's default limit is in the low thousands) specifically to turn a silent memory blowout into a clean error. The function is not buggy - it is merely too deep for a linear walk. The right move here is not "recurse harder"; it is to use a loop.

> Raising the recursion limit (for example, Python's `sys.setrecursionlimit`) is almost always the wrong fix. You are not solving the depth problem, you are moving the cliff edge a little further out - and risking a real, uncatchable crash if you overshoot the actual stack memory. If depth is the problem, change the algorithm.

## Recursion versus iteration

Here is the plain truth: any recursion can be rewritten as a loop, and any loop can be rewritten as recursion. They are equally powerful. The choice is about which one makes the code clearer and which one fits in memory.

The same countdown, as a loop:

```python runnable
def countdown(n):
    while n > 0:        # the loop condition IS the base case, inverted
        print(n)
        n -= 1          # the same shrink step, just in place
    print("liftoff")

countdown(3)
```

*What just happened:* identical behavior, no stack growth. The `while` condition plays the role of the base case, and `n -= 1` plays the role of the shrink step. Notice the parts did not disappear - they are the same two ideas, written as a loop instead of as calls. A loop uses one stack frame no matter how many times it runs, so it never overflows on depth.

So when do you reach for which?

- **Prefer a loop** when the work is a straight linear walk - summing, counting, scanning a flat list. It is clearer to most readers and it cannot overflow.
- **Prefer recursion** when the structure is itself nested or branching - trees, nested data, "this thing contains smaller versions of this thing." Forcing that into a loop means hand-managing your own stack, which is more code and more bugs.
- **If recursion is the clear fit but depth is a risk** (a very deep tree), you can convert to an iterative version with an explicit list acting as the stack - you do by hand what the call stack did for free, but you control the memory.

```text
linear, flat data          -> loop        (clear, no overflow)
nested / branching data     -> recursion   (matches the shape)
nested data, but very deep  -> explicit stack loop (control the memory)
```

*What just happened:* this is the decision in three lines. Match the tool to the shape of the data first; only reach for the explicit-stack version when a naturally-recursive problem is also dangerously deep.

## For builders

In day-to-day code, most recursion you write is shallow and safe - walking a config tree, a DOM, a modest folder hierarchy. The depth limit only bites when the structure can grow without bound (user-supplied nesting, a linked list of every event ever) or when you accidentally recurse over a flat collection that should have been a loop. When you read a `RecursionError` in production, your first two questions are always the same: *is the base case ever reached*, and *is this depth legitimate or should this have been a loop?* That diagnosis covers nearly every case you will hit.

```quiz
[
  {
    "q": "A recursive function has a correct base case but still crashes with a stack overflow. What is the most likely cause?",
    "choices": ["The base case returns the wrong value", "The recursive call does not move the input closer to the base case", "Recursion is disabled in the language", "The function name is misspelled"],
    "answer": 1,
    "explain": "A base case only helps if every call shrinks toward it; if the input never changes, the base case is never reached."
  },
  {
    "q": "A correct recursive sum works on a small list but raises RecursionError on a list of 100,000 items. The best fix is:",
    "choices": ["Raise the recursion limit as high as possible", "Rewrite it as a loop", "Add a second base case", "Call it twice"],
    "answer": 1,
    "explain": "The function is fine but too deep; a loop uses one stack frame regardless of length and cannot overflow on depth."
  },
  {
    "q": "When is iteration (a loop) generally the better choice over recursion?",
    "choices": ["For walking trees and nested structures", "For a straight linear walk over flat data", "Whenever the input is large and nested", "Never; recursion is always better"],
    "answer": 1,
    "explain": "Loops are clearer and overflow-proof for linear work; recursion shines when the data itself is nested or branching."
  }
]
```