---
title: "Recursion"
url: https://algopath.pro/patterns/recursion
language: en
summary: "A function that calls itself on a smaller version of the same problem. A base case stops it, and the calls unwind back up."
updated: 2026-08-24
---

# Recursion

A function that calls itself on a smaller version of the same problem. A base case stops it, and the calls unwind back up.

## How does Recursion work?

Find the smallest case you can answer with no work at all. That is the base case.

Assume the function already works on a smaller input. You trust it rather than tracing it.

Write one step that makes the problem smaller. Then call yourself on what is left.

Combine the returned result with that one step. Those two lines are the whole body.

Every call takes a frame of memory. Depth n means n frames are alive at once.

Without a base case the calls never stop. The stack fills and the program dies.

- `sum([2, 4, 6])` The list is not empty. Take the 2 and ask for the rest.
- `sum([4, 6])` Take the 4 and ask again. The list keeps shrinking.
- `sum([6])` One element is left. This is still not the base case.
- `sum([]) = 0` The empty list is the base case. It answers with no work.
- `0, 6, 10, 12` The results unwind back up. Each call adds its own value.

## When should you use Recursion?

- problem is defined in terms of a smaller version of itself
- nested/tree-shaped structure to walk (directory, expression, linked list)
- compute a count/sum/depth over all sub-elements
- natural base case + recursive case split (factorial, Fibonacci, tree depth)

## What is Recursion confused with?

- **Recursion with memoization** - Memoisation is this plus a cache of past answers. Add it once the same argument comes back.
- **Backtracking** - Backtracking undoes a choice after exploring it. Plain recursion never undoes anything.
- **Stack (LIFO)** - The call stack is a stack you did not write. Writing your own removes the depth limit.
- **Tree traversal** - Trees are where recursion is cheapest and clearest. That page is about the three visit orders.

## What is the time and space complexity of Recursion?

Depth up to roughly 10000 is safe in a browser. Deeper than that, rewrite the recursion as a loop.

## A worked example of Recursion

### Flatten a nested array

You get an array whose items are either numbers or more arrays. Return one flat array of numbers.

The nesting can go to any depth at all.

A number is the base case, so it is returned as it is.

An array is the smaller problem: flatten each item and join the pieces. The depth handles itself.

```javascript
function flatten(items) {
    const result = [];

    for (const item of items) {
        if (Array.isArray(item)) {
            // trust the call to handle every depth below this one
            result.push(...flatten(item));
        } else {
            result.push(item);
        }
    }

    return result;
}
```

## Common mistakes with Recursion

- **No base case, or the wrong one** The calls then run until the stack fills up. Write the base case before anything else.
- **Not shrinking the input** Every call has to move closer to the base case. Passing the same argument loops forever.
- **Recursing far too deep** A list of a million nodes needs a million frames. Rewrite that as a loop.
- **Sharing one mutable array between calls** A child call can change what the parent still needs. Copy it, or undo the change on the way out.

## Which interview problems use Recursion?

- **Factorial and Fibonacci** The classic shape, though Fibonacci needs a cache.
- **Reverse a string** Swap the two ends, then recurse on the middle.
- **Flatten a nested list** A plain value is the base case.
- **Merge two sorted lists** Take the smaller head and recurse on the rest.
- **Power of a number** Halve the exponent instead of subtracting one.
- **Tower of Hanoi** Two smaller moves wrapped around one direct move.
- **Maximum depth of a binary tree** One plus the deeper of the two children.

## JavaScript

```javascript
function recurse(n) {
    if (n <= 0) return 0; // base case
    return n + recurse(n - 1); // recursive case: smaller subproblem
}
```

## Python

```python
def recurse(n):
    if n <= 0:
        return 0  # base case
    return n + recurse(n - 1)  # recursive case: smaller subproblem
```

## PHP

```php
function recurse(int $n): int {
    if ($n <= 0) return 0; // base case
    return $n + recurse($n - 1); // recursive case: smaller subproblem
}
```