Learn · DSA · Pattern 6

Recursion & Backtracking

A function that solves a big problem by calling itself on a smaller piece — until the piece is tiny enough to answer directly. It feels like magic until you see the stack; then it’s just bookkeeping.

Before we start

📋 What you’ll learn

What recursion is: a function that calls itself
The two parts every recursion needs (base + recursive case)
How the “call stack” actually works
Backtracking: try → recurse → undo

✅ After this you’ll be able to

Write a recursive solution and know it will terminate
Trace what the call stack is doing
Recognise problems that break into smaller same-shaped pieces

Why you’re learning it: trees, graphs, combinations and “divide and conquer” all run on recursion. Get comfortable here and the hard-looking problems get simple. ⏱️ ~30 min.

The idea

Picture Russian nesting dolls. To open them all: open this one, then do the exact same thing to the smaller doll inside — and stop when you reach the tiny solid one. That “do the same thing to a smaller version, and stop at the smallest” is recursion. Every recursion needs two things:

🛑 Base case

The smallest version you can answer immediately — the solid doll. Without it, the function calls forever and crashes (“stack overflow”).

🔁 Recursive case

Do a little work, then call yourself on a smaller input — trusting it’ll solve the rest.

Watch it work — factorial(4)

factorial(n) = n × factorial(n − 1), and factorial(1) = 1 (the base case). Calls stack up, then resolve back down:

factorial(4)
 = 4 × factorial(3)
 = 4 × (3 × factorial(2))
 = 4 × (3 × (2 × factorial(1)))     ← base case hit, returns 1
 = 4 × (3 × (2 × 1))                ← now it unwinds back up
 = 4 × (3 × 2)
 = 4 × 6
 = 24

The stack builds on the way down (each call waits), then collapses on the way up as each returns.

Backtracking — recursion that explores

For problems like “all combinations” or a maze: try a choice, recurse deeper, and if it fails, undo the choice and try the next. Try → recurse → undo. It quietly explores every path without you writing nested loops.