# Recursion, or how to think in smaller problems

A function that calls itself is not a trick. It is a way of describing a
problem by what remains after you take one step.

Before reading on, revisit [the loop chapter](../tables.demo.md) and make sure
you can trace `fib(5)` by hand. Every recursive definition has two parts: the
case you can answer immediately, and the case that gets you closer to it.

> [!note]
> Write the base case first. If you cannot say when to stop, you do not yet
> understand the problem.

```js
function fib(n) {
  if (n < 2) return n
  return fib(n - 1) + fib(n - 2)
}
```

| Call     | Returns | Depth |
| -------- | ------- | ----- |
| `fib(0)` | 0       | 1     |
| `fib(3)` | 2       | 3     |
| `fib(5)` | 5       | 5     |

The lab is due Thursday.

[@link.button Start the lab](../tasks.demo.md)

---

## Why the base case comes first

Most recursion bugs are stopping bugs. Write the case you can answer without
help, then describe one step toward it.

- Name the smallest input the function must handle.
- Say what the function returns for that input.
- Only then write the call that shrinks the problem.

> A recursive definition is a promise: if the smaller case works, this one
> does too.

### Tracing by hand

1. Write the call at the top of a page.
2. Under it, write every call it makes.
3. Resolve from the bottom up, filling in return values.

> [!tip] A practical tip
> Draw the tree once. After that, trust the base case and stop drawing.

> [!warning]
> Recursion without a base case does not loop forever. It runs out of stack.

---

## Small details, real interactions

> [!note]- Show a worked example
> `fib(3)` expands to `fib(2) + fib(1)`. The base cases stop both branches.

[@link.button Start the lab](../tasks.demo.md) ·
[@link.button.outline Review the table](../tables.demo.md)

Tab through the links and disclosure to see keyboard focus. Open the example,
then compare the same content in Focus and Slides using Player.