Recursion

Before reading — explore the Recursion visualizer to see how the call stack builds up and unwinds step by step.

Let's learn recursion in the simplest way possible.

What is recursion?

You already know that a function can call another function. Well, a function can also call itself. That's it. That's recursion.

void callMe() {
    callMe();
}

That's the programmer's definition. But it doesn't really tell you why this is useful. So let's understand it properly with an analogy.

The line at the ticket counter

Imagine you're standing in a long line, and you want to know how many people are ahead of you. You can't see the front of the line, so you can't just count.

What do you do? You turn to the person right in front of you and ask, "How many people are ahead of you?"

That person doesn't know either. So they turn around and ask the person in front of them. That person asks the one in front of them. And so on, all the way down the line.

Eventually, the question reaches the very first person. They look ahead, see nobody, and say, "Zero people ahead of me."

Now the answer travels back down the line. The second person hears "0," adds 1 for themselves, and says "1 person ahead of me." The third person hears "1," adds 1, and says "2." This keeps going, each person adding 1 before passing the answer back — until it finally reaches you.

Notice what just happened. Nobody in that line did any heavy lifting. Every single person did the exact same tiny task: ask the person in front, then add 1 to whatever they say back. The line kept breaking the question into a smaller version of itself, until it reached a point where there was nothing left to break down — and that's where the answers started flowing back.

That's exactly how recursion works in code.

The one rule of recursion

Here's the one thing to remember. Tattoo it on your brain if you have to:

Every recursive function you'll ever write is built from two pieces:

Base case — the point where no more work is needed, and the function can just answer directly. In our line example, this is the first person, who doesn't need to ask anyone.

Recursive case — the smallest possible step of "real" work, followed by a call to a smaller version of the same problem. In our line example, this is "ask the person in front of you, then add 1."

Without a base case, the recursion would never stop. We'll see exactly what happens when that goes wrong a little later.

A simple example: factorial

The factorial of a number is what you get when you multiply every whole number from that number down to 1.

So the factorial of 5 (written 5!) is:

5 × 4 × 3 × 2 × 1 = 120

Here's the interesting bit. 5! can also be written as:

5 × 4!

And 4! can be written as 4 × 3!. And 3! as 3 × 2!. See the pattern? Each factorial is just a number multiplied by the factorial of one less than it. That's the recursive case.

This can't go on forever though — it has to stop somewhere. And by definition, 1! = 1 and 0! = 1. There's no smaller number to multiply by, so this is our base case.

Putting that into words:

• Recursive case: n! = n × (n - 1)!
• Base case: 1! = 1 and 0! = 1

Now let's turn that into code.

int fact(int n) {
    // base case — no work required
    if (n == 0 || n == 1) {
        return 1;
    }

    // recursive case — smallest step of work, then call a smaller version
    return n * fact(n - 1);
}

if (n == 0 || n == 1) return 1;
This is our base case. The moment we hit 0 or 1, we stop calling ourselves and just return an answer directly.

return n * fact(n - 1);
This is our recursive case. We do the smallest bit of work we can — multiplying by n — and hand off the rest of the problem, (n - 1)!, to another call of the same function.

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * fact(n - 1);
}

int main() {
    cout << fact(5);
    return 0;
}
// 120

Tracing it — the call stack

Let's actually watch what happens when we call fact(5).

Every time a function calls another function (even itself), the computer doesn't finish the first call. It pauses it and stacks the new call right on top — like a stack of plates. It can only work on the plate at the very top.

fact(5)  →  needs 5 * fact(4)
fact(4)  →  needs 4 * fact(3)
fact(3)  →  needs 3 * fact(2)
fact(2)  →  needs 2 * fact(1)
fact(1)  →  hits base case, returns 1

Each call is stuck waiting, because it needs the answer from the call above it before it can finish its own multiplication. fact(5) can't return anything until fact(4) returns. fact(4) can't return until fact(3) returns. This keeps going until we hit fact(1) — our base case — which doesn't need to wait on anyone. It just answers: 1.

Now the stack starts unwinding, one plate at a time, from the top:

fact(1) returns 1
fact(2) returns 2 * 1  = 2
fact(3) returns 3 * 2  = 6
fact(4) returns 4 * 6  = 24
fact(5) returns 5 * 24 = 120

And there's our answer: 120.

This "build up, then unwind" pattern is the heart of recursion. Calls stack up while going down toward the base case, then each one resolves and hands its answer back up, one level at a time.

Why the base case actually matters

Let's see what happens when we forget the base case entirely.

void printFive() {
    cout << 5 << endl;
    printFive();
}

Run this, and you won't get an infinite stream of 5s forever. You'll get a bunch of 5s, and then:

5
5
5
...
Segmentation fault (core dumped)

Here's why. Every function call — recursive or not — takes up a little bit of memory on the call stack, to remember where to return to once it's done. That stack has a limited size.

Since printFive() never hits a base case, it never gets to unwind and free up any of that memory. It just keeps stacking new calls on top, one after another, until the stack runs completely out of room. At that point, the program crashes with a stack overflow.

So the base case isn't just a nice-to-have. It's what tells the computer "stop stacking, start unwinding." Without it, recursion has nowhere to go but down, until it runs out of space.

Another example: checking a palindrome

A palindrome is a word that reads the same forwards and backwards — like racecar.

Let's think about how to check this recursively, the same way we broke down factorial.

Recursive case (smallest step of work): Check if the first and last letters match. If they do, strip them off and check what's left.

Base case (no work required): If there's one letter left, or none at all, it's automatically a palindrome — there's nothing left to compare.

bool isPalindrome(string text) {
    // base case
    if (text.length() == 0 || text.length() == 1) {
        return true;
    }

    // recursive case
    if (text[0] == text[text.length() - 1]) {
        return isPalindrome(text.substr(1, text.length() - 2));
    }

    return false;
}

if (text.length() == 0 || text.length() == 1) return true;
Our base case. Zero or one letters left means we've run out of things to compare — so it must be a palindrome.

if (text[0] == text[text.length() - 1])
We compare the first and last characters.

return isPalindrome(text.substr(1, text.length() - 2));
If they match, we call the function again — but this time on the string with the first and last letters removed. A smaller version of the same problem.

return false;
If the first and last letters don't match, we can stop immediately — it's not a palindrome.

Let's trace isPalindrome("racecar"):

"racecar"  →  r == r  →  check "aceca"
"aceca"    →  a == a  →  check "cec"
"cec"      →  c == c  →  check "e"
"e"        →  base case (1 letter)  →  true

Each true travels back up, so the final result is true.

#include <iostream>
using namespace std;

bool isPalindrome(string text) {
    if (text.length() == 0 || text.length() == 1) {
        return true;
    }
    if (text[0] == text[text.length() - 1]) {
        return isPalindrome(text.substr(1, text.length() - 2));
    }
    return false;
}

int main() {
    cout << isPalindrome("racecar");
    return 0;
}
// 1  (true)

A more useful example: Tower of Hanoi

Before reading — explore the Tower of Hanoi visualizer to watch the disks move step by step.

Factorial and palindromes are great for learning the shape of recursion. But let's be honest — you'd probably never actually use recursion to solve either of those in real life. So let's look at a problem where recursion isn't just a nice trick, it's genuinely the easiest way to think about the solution.

The puzzle

There's an old story about monks in a temple with three tall pegs. On the first peg sits a stack of 64 golden disks, each one smaller than the one below it — like a little pyramid. The monks' job is to move the entire stack to the third peg, one disk at a time, following two rules:

1. You can only move one disk at a time, and only the top disk off any peg.
2. You can never place a bigger disk on top of a smaller one.

Legend says that when the monks finish, the world ends. (No pressure.) This puzzle is called the Tower of Hanoi, and we're going to solve it — hopefully without ending the world.

Let's start small. Forget 64 disks — imagine just 3 disks, sitting on peg A, and we want to move them all to peg C, using peg B as a helper.

Peg A        Peg B        Peg C
 [3]
 [2]
 [1]
 ───         ───          ───

Thinking about it recursively

Here's the trick. Don't think about moving 3 disks. Think about moving just the bottom disk.

The biggest disk on peg A is disk 3. It's stuck at the bottom, and it can't go anywhere until every disk sitting on top of it is out of the way. So really, before we can even touch disk 3, we need to move the 2 disks sitting on top of it (disks 1 and 2) somewhere else entirely — out of the way, onto peg B.

Once disks 1 and 2 are safely parked on peg B, peg A has only disk 3 left, sitting alone. Nothing stops us from moving it straight to peg C.

And now — disks 1 and 2 are sitting on peg B, and disk 3 (the biggest one) is already home on peg C. So the very last step is simply moving those 2 disks from peg B onto peg C, right on top of disk 3.

Notice something? "Move 2 disks from A to B" and "move 2 disks from B to C" are just smaller Towers of Hanoi problems. Same puzzle, fewer disks. That's our recursive case.

So, in plain English, moving n disks from a source peg to a destination peg, using a helper peg, always breaks down into 3 steps:

1. Move the top n - 1 disks from source to helper (using destination as the helper this time).
2. Move the one remaining disk from source to destination directly.
3. Move those n - 1 disks from helper to destination (using source as the helper this time).

And the base case? If there are 0 disks to move, there's nothing to do at all — we just stop.

The code

void hanoi(int n, char source, char destination, char helper) {
    // base case — no disks left to move
    if (n == 0) {
        return;
    }

    // move n - 1 disks out of the way, onto the helper peg
    hanoi(n - 1, source, helper, destination);

    // move the one remaining (biggest) disk directly
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;

    // move the n - 1 disks from the helper peg onto their final home
    hanoi(n - 1, helper, destination, source);
}

if (n == 0) return;
Our base case. Zero disks means there's nothing left to move, so we stop right here.

hanoi(n - 1, source, helper, destination);
Step 1 — get everything except the bottom disk out of the way, parking it on the helper peg.

cout << "Move disk " << n ...
Step 2 — with the smaller disks out of the way, the biggest disk left on source can move directly to destination.

hanoi(n - 1, helper, destination, source);
Step 3 — bring those smaller disks from the helper peg over to their final home, on top of the disk we just placed.

#include <iostream>
using namespace std;

void hanoi(int n, char source, char destination, char helper) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, source, helper, destination);
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    hanoi(n - 1, helper, destination, source);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}
// Move disk 1 from A to C
// Move disk 2 from A to B
// Move disk 1 from C to B
// Move disk 3 from A to C
// Move disk 1 from B to A
// Move disk 2 from B to C
// Move disk 1 from A to C

Tracing it

Run this by hand for hanoi(3, A, C, B) and here's what unfolds:

hanoi(3, A→C, helper B)
 ├─ hanoi(2, A→B, helper C)
 │   ├─ hanoi(1, A→C, helper B)
 │   │   ├─ hanoi(0, A→B) → base case, does nothing
 │   │   ├─ Move disk 1 from A to C
 │   │   └─ hanoi(0, C→B) → base case, does nothing
 │   ├─ Move disk 2 from A to B
 │   └─ hanoi(1, C→B, helper A)
 │       ├─ hanoi(0, C→A) → base case, does nothing
 │       ├─ Move disk 1 from C to B
 │       └─ hanoi(0, B→A) → base case, does nothing
 ├─ Move disk 3 from A to C
 └─ hanoi(2, B→C, helper A)
     ├─ hanoi(1, B→A, helper C)
     │   └─ Move disk 1 from B to A
     ├─ Move disk 2 from B to C
     └─ hanoi(1, A→C, helper B)
         └─ Move disk 1 from A to C

Seven moves total, and every single one of them is legal — no big disk ever lands on a smaller one. And notice we never actually had to "think ahead" about the whole puzzle. We only ever had to answer one small question at a time: move these disks out of the way, move the big one, move them back. Recursion handled the rest.

Time complexity

Here's where Tower of Hanoi gets interesting. Every call to hanoi(n) makes 2 more calls to hanoi(n - 1). So the number of moves roughly doubles every time we add one more disk:

1 disk  →  1 move
2 disks →  3 moves
3 disks →  7 moves
4 disks →  15 moves
n disks →  2ⁿ - 1 moves

That means the time complexity is O(2ⁿ) — exponential. For 3 disks, that's fine, only 7 moves. But for the monks' legendary 64 disks? That's over 18 quintillion moves. Even at one move per second, that outlasts the sun. (So don't worry — the world isn't ending any time soon.)

This is also a nice reminder that recursion being elegant doesn't mean it's fast. Some problems are just expensive no matter how you solve them — recursion just makes the expensive part easy to see.

Time complexity

For fact(n), we make one call for every number from n down to 1. That's n calls total, and each call does a constant amount of work (one multiplication). So the time complexity is O(n).

The same logic applies to isPalindrome. Each call strips two characters and moves on, so for a string of length n, we make roughly n / 2 calls — which is still O(n).

When should you use recursion?

Recursion isn't automatically better than a loop. Every recursive call takes up space on the call stack, so a recursive solution can use more memory than a loop that does the same job.

That said, recursion tends to shine when a problem is naturally made up of smaller versions of itself — trees, graphs, and divide-and-conquer problems are the classic examples. In those cases, writing the same logic with loops can get messy fast, while the recursive version often mirrors exactly how you'd describe the problem in plain English.

Where is recursion used?

File systems. Opening a folder that contains folders, that contain more folders — file explorers use recursion to dig through every level until they hit a folder with no subfolders left (the base case).

Trees and graphs. Structures like binary trees are naturally recursive — a tree is just a node with smaller trees attached to it. Exploring them recursively is often the most natural approach.

Divide and conquer algorithms. Algorithms like Merge Sort and Quick Sort work by splitting a problem in half, solving each half recursively, and combining the results.

Classic puzzles and backtracking. Problems like Tower of Hanoi, solving a maze, or generating every possible combination of something all follow the same shape — break the problem into a smaller version of itself, solve that, and combine the results.

Summary

Recursion is a function calling a smaller version of itself, over and over, until it reaches a base case simple enough to answer directly. Every recursive function needs two things: a base case that stops the calls, and a recursive case that does a small piece of work and hands off the rest. Skip the base case, and the call stack fills up until the program crashes.

Factorial showed us the basic shape. Palindrome checking showed us recursion working on a string. And Tower of Hanoi showed us the real payoff — a problem that would be genuinely messy to solve with loops, but almost writes itself once you think about it recursively. Get comfortable with that shift in thinking, and recursion turns problems that are naturally repetitive — trees, folders, puzzles, divide-and-conquer — into code that reads almost exactly like the problem itself.