What is recursion? A function that calls itself, explained

Recursion is a way of solving a problem by solving a smaller copy of the same problem, and then a smaller copy of that, until the copy is so small its answer is obvious. In programming, it means a function that calls itself. Every working recursion needs two parts: a base case, where it stops and answers outright, and a recursive case, which hands a smaller version of the problem back to itself.

In short

• A recursive function solves a big problem by calling itself on a smaller piece, then combining the answers.
• The base case is the stop: without one, the calls never end and the program crashes.
• Recursion is natural for anything built from smaller copies of itself, such as folders, trees and sentences, but a careless version can repeat work and be very slow.

How does recursion work, in everyday terms?

Picture a long queue at a cinema, and you want to know your place in it without leaving. You ask the person in front, "what's your place?" They don't know either, so they ask the person in front of them, and so on to the front. The first person in the queue can answer outright: "I'm number 1." That is the base case. The answer then travels back: the second person says 2, the third says 3, until it reaches you, and you add one to whatever you were told.

That picture holds the two halves of every recursion. On the way in, each step passes a smaller problem along and waits. On the way back out, each step takes the answer it was given and does a little work with it. Nobody in the queue needs to see the whole line; each only needs to know how to ask and how to add one. A recursive solution only has to say how to make the problem one step smaller, and what to do at the very smallest.

How does a function call itself? Factorial, step by step

The factorial of a positive whole number is that number multiplied by every whole number below it, down to 1. The factorial of 4 is 4 × 3 × 2 × 1 = 24. It can be written in terms of itself: the factorial of n is n times the factorial of n − 1, and the factorial of 1 is 1. As a function in Python:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

Here is every call when the program asks for factorial(4).

1. factorial(4) can't answer yet. It needs 4 × factorial(3), so it calls factorial(3) and waits.
2. factorial(3) needs 3 × factorial(2). It calls and waits.
3. factorial(2) needs 2 × factorial(1). It calls and waits.
4. factorial(1) is the base case. It returns 1 straight away.
5. factorial(2) now has its answer: 2 × 1 = 2.
6. factorial(3): 3 × 2 = 6.
7. factorial(4): 4 × 6 = 24.

While this runs, four calls are waiting at once, each remembering its own n. The computer keeps them on the call stack, a data structure where the most recent call sits on top and is finished first. Each waiting call takes a little memory, which is why recursion that goes too deep fails. Python stops at 1,000 waiting calls by default, a limit its documentation says exists to stop runaway recursion from crashing the program. Leave out the base case, and factorial(4) would call factorial(3), 2, 1, 0, −1 and on, until it hit that limit.

Why is the obvious Fibonacci code so slow?

The Fibonacci sequence starts 0, 1, and each number after is the sum of the two before: 0, 1, 1, 2, 3, 5, 8, 13. Its definition is already recursive, fib(n) = fib(n − 1) + fib(n − 2), with fib(0) = 0 and fib(1) = 1 as base cases, and it can be typed into code almost word for word. That code is correct, and it is very slow.

The trouble is that each call makes two more. To get fib(5), the function asks for fib(4) and fib(3). But fib(4) asks for fib(3) again, and fib(2), and each fib(3) asks for fib(2) again. The calls branch like a tree, and the same small answers are worked out over and over. Counting every call, run in Python:

Asked for	Answer	Calls made, plain recursion	Values computed, with memoization
fib(5)	5	15	6
fib(10)	55	177	11
fib(20)	6,765	21,891	21
fib(30)	832,040	2,692,537	31

The plain version makes nearly 2.7 million calls to compute fib(30), and the count grows by about 1.6 times, the golden ratio, for each step up in n, as the classic MIT textbook Structure and Interpretation of Computer Programs shows. In Big O terms that is exponential growth. By fib(50) it would take about 40 billion calls.

The fix is memoization: keep a note of every answer already worked out, and look it up instead of computing it again. Then fib(30) needs only one real calculation for each n from 0 to 30: 31 in all, against 2,692,537. Python has it built in: putting @functools.lru_cache above the function, as its functools documentation describes, turns the slow version into the fast one without changing a line inside it. Recursion wasn't the problem; repeating work was.

Where does recursion show up outside code?

Anywhere a thing is made of smaller things of the same kind. A folder holds files and other folders, so the size of a folder is the size of its files plus the size of each folder inside it, which is exactly how software adds it up. A tree in a database or a family history is a root with smaller trees beneath it. A sentence can hold another sentence ("she said that he thought that it rained"), and grammars describe that with recursive rules.

Mathematics uses the same idea to prove things. A proof by induction, a kind of mathematical proof, shows a statement is true for 1, then shows that if it is true for any number it is true for the next; together those cover every whole number, the way the queue covered every person. Fractals such as the Koch snowflake are drawn by replacing each line with a smaller pattern of lines, again and again, and Russian dolls nest smaller dolls inside, with the smallest, solid one as the base case.

What do people get wrong about recursion?

The first mistake is to think a definition in terms of itself must be circular. It isn't, as long as each call is on something smaller and the shrinking always reaches the base case. "To understand recursion, you must first understand recursion" is a joke precisely because it has no base case and nothing gets smaller.

The second is to treat recursion as either clever or wasteful in itself. Any recursive algorithm can be rewritten as a loop with a stack of its own, and the factorial above is clearer as a loop. But for folders, trees and the fast sorting methods such as merge sort, which split a list in half, sort each half the same way, and merge them, the recursive version is the natural one, and the loop version is the one that's hard to read.

Check yourself

• Without looking back, name the two parts every recursive function needs, and what goes wrong without the first.
• Trace factorial(3) call by call, on the way in and on the way out.
• Why does plain recursive Fibonacci make millions of calls, and how does memoization cut them to a few dozen?

Sources

• Recursion (computer science) — Wikipedia
• Procedures and the processes they generate, in Structure and Interpretation of Computer Programs — Harold Abelson and Gerald Jay Sussman, MIT Press, 1996
• sys, system-specific parameters and functions — Python Software Foundation
• functools, higher-order functions and operations on callable objects — Python Software Foundation