Programming · concepts · recursion

What is recursion?

Some problems are naturally self-similar: a folder contains folders, a sentence is made of clauses made of words, a big sum is just one number plus a smaller sum. Recursion is the programming technique that matches this shape directly — a function that solves a problem by calling itself on a smaller version of the same problem. This guide explains what recursion really is, the two ingredients every recursive function needs, real code examples, how it compares to loops, what tail recursion is, the classic pitfalls, and why it sits at the heart of functional programming.

The short definition

Recursion is when a function calls itself to solve a problem by reducing it to one or more smaller instances of the same problem. Each call handles a slightly smaller piece, and the calls keep going until the problem is small enough to answer directly. At that point the answers combine back up to solve the original problem.

The two ingredients

Every correct recursive function has exactly two parts. Miss either one and it breaks.

1. The base case. This is the smallest version of the problem that you can answer without recursing — it stops the recursion. For a factorial, the base case is 0! = 1. For summing a list, the base case is the empty list, whose sum is 0.

2. The recursive case. This handles the general problem by doing a little work and then calling the function again on a smaller input — one that moves closer to the base case. The key word is smaller: if the recursive call isn't on a genuinely smaller problem, you never reach the base case.

Without a reachable base case, a recursive function calls itself forever. In practice it doesn't loop infinitely in silence — it exhausts the program's call stack and crashes with a stack overflow.

A first example: factorial

The factorial of a number n (written n!) is n × (n-1) × … × 1. It has an obvious recursive structure: n! = n × (n-1)!, and 0! = 1. In Python:

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case, on a smaller n

factorial(5)   # 120

Trace it: factorial(5) waits for factorial(4), which waits for factorial(3), down to factorial(0), which returns 1 directly. Then the answers multiply back up: 1 → 1 → 2 → 6 → 24 → 120. The same idea in Haskell, where recursion is the everyday tool for this kind of loop:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

More examples

Summing a list. The sum of a list is its first element plus the sum of the rest; the sum of an empty list is zero.

# Python
def total(xs):
    if not xs:          # base case: empty list
        return 0
    return xs[0] + total(xs[1:])

total([3, 1, 4, 1])     # 9

-- Haskell
total :: [Int] -> Int
total []     = 0
total (x:xs) = x + total xs

Walking a tree. Recursion shines on nested, self-similar data — exactly where loops get awkward. To count nodes in a binary tree, count this node plus the nodes in each subtree:

# Python: a node is a dict with optional left/right children
def count_nodes(node):
    if node is None:        # base case: empty subtree
        return 0
    return 1 + count_nodes(node["left"]) + count_nodes(node["right"])

Notice the same shape every time: a base case for the smallest input, and a recursive case that combines results from smaller inputs.

Recursion vs iteration

Anything you can write with recursion you can also write with a loop (iteration), and vice versa — they're equally powerful. The choice is about clarity and cost.

Recursion often reads more naturally for self-similar problems (trees, nested structures, divide-and-conquer algorithms like quicksort or merge sort). The downside is that each call consumes a stack frame, so deep recursion can use a lot of memory or overflow the stack.

Iteration (a for or while loop) uses constant stack space and is usually faster in languages that don't optimise recursive calls. It can be clearer for simple, linear "do this N times" work. The factorial above is a good example: a loop computes it with no stack growth at all.

Rule of thumb: reach for recursion when the data or algorithm is naturally recursive and the depth is bounded; reach for a loop when the work is flat and you care about raw performance or very deep iteration.

Tail recursion and why it matters

A recursive call is in tail position when it's the very last thing the function does — its result is returned directly, with no further work waiting on it. The first factorial above is not tail-recursive: after factorial(n - 1) returns, there's still a multiplication left to do, so each call must stay on the stack. You can rewrite it to carry the running result in an accumulator, so the recursive call is the last step:

def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n - 1, acc * n)   # tail call: nothing left to do after

When the recursive call is in tail position, a compiler can perform tail-call optimisation (TCO): reuse the current stack frame instead of pushing a new one, turning the recursion into something as cheap as a loop and removing the stack-overflow risk. Whether this happens depends on the language: Scheme and many functional languages guarantee TCO, and Haskell's lazy, GHC-optimised model often handles accumulating recursion efficiently. Crucially, CPython does not do TCO — Python keeps every frame and even caps recursion depth (about 1000 by default), so the tail-recursive version above gives no benefit in Python and a plain loop is the idiomatic choice there. Always check your language before relying on deep tail recursion.

Common pitfalls

Missing or unreachable base case. The number-one bug. If no call ever hits the base case (or the input doesn't actually shrink), you get infinite recursion and a stack overflow.

Too much depth. Even correct recursion can overflow on very large inputs in languages without TCO. If you might recurse tens of thousands of levels deep, prefer iteration or an explicit stack.

Redundant work. The naïve recursive Fibonacci recomputes the same values over and over:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # recomputes overlapping subproblems

This branches into roughly two calls at every level, so its running time grows exponentially — fib(40) already makes hundreds of millions of calls. The fix is memoisation: cache each result the first time you compute it so repeated subproblems are answered instantly.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # each n now computed once

With caching, the same recursion runs in linear time. The lesson: recursion describes what to compute clearly, but you still have to watch how much work the calls actually duplicate.

Recursion and functional programming

In functional programming, recursion does a lot of the heavy lifting that loops do in imperative code. Because pure functional style avoids mutable loop counters and in-place updates, repeating work is expressed by a function calling itself over smaller data — exactly the list and tree examples above. Languages like Haskell lean on recursion (and on higher-order helpers like map and fold that are themselves recursive underneath), and Haskell's lazy evaluation even lets recursion define infinite structures that are only computed as far as you actually read them.

FAQ

What is recursion in simple terms? It's a function that solves a problem by calling itself on a smaller version of the same problem, stopping when it reaches a case small enough to answer directly.

What is a base case? The simplest input a recursive function can answer without recursing further. It's what stops the recursion — without a reachable base case the function calls itself forever and crashes.

Is recursion better than loops? Neither is universally better. Recursion is clearer for self-similar, nested problems; loops use constant stack space and are often faster for flat, linear work. Many problems are written either way.

What is tail recursion? Recursion where the recursive call is the last action the function performs. Languages that support tail-call optimisation can run it in constant stack space, like a loop, avoiding stack overflow.

Why does my recursion cause a stack overflow? Usually a missing or unreachable base case (the input never shrinks to it), or simply recursing deeper than the call stack allows. Check that every recursive call moves toward the base case, and switch to iteration for very deep work.

Recursion is one of the fundamental ways to express computation — it's a close cousin of how we describe any algorithm as smaller, repeatable steps, and it depends on understanding how a variable like an accumulator carries state between calls. Browse more clear explainers in our guides index.

Frequently asked questions