After covering the foundational building blocks in Session 1, the next step is one of the most important problem-solving techniques in all of programming: recursion.
And once recursion feels comfortable, it unlocks a powerful search strategy called backtracking.
These two concepts appear everywhere in competitive programming — Fibonacci, binary search, tree traversal, merge sort, dynamic programming, N-Queens, and more. They deserve their own spotlight. 🌟
What Is Recursion?
A function is recursive if it calls itself. Instead of solving a problem in one go, a recursive function breaks it into a smaller version of the same problem, solves that, and repeats — until the problem becomes simple enough to answer directly.
Three things define every recursive solution:
- The problem is expressed in terms of a smaller instance of itself
- Each call reduces the problem size
- There is a point where the problem becomes trivial and no further calls are needed — this is the base case
The Nested Box Analogy
Think of recursion like opening nested boxes. A big box contains a smaller box, which contains another, and so on. Eventually you find the item you were looking for. That innermost box is the base case. Without it, you would keep opening boxes forever — which is how you get a stack overflow, not a solution.
Base Case and Recursive Case
Every recursive function has exactly two parts:
Recursive case — the problem is reduced in size and the function calls itself again.
Base case — the terminating condition. No further recursive call is made. The function returns a direct answer.
Both are non-negotiable. A function without a base case will keep calling itself, consuming stack memory until the program crashes.
Example: Factorial
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 ← base case
Each step reduces the problem by one. When the function hits 1! = 1, it stops, and the results unwind back up the call stack.
In pseudocode:
function factorial(n):
if n == 1:
return 1 # base case
return n * factorial(n - 1) # recursive case
What Happens in Memory?
Every recursive call creates a new stack frame — a temporary block of memory storing that call's local variables and the point to return to once it finishes.
For factorial(4), the call stack builds up like this:
factorial(4)
└── factorial(3)
└── factorial(2)
└── factorial(1) → returns 1
Then it unwinds:
factorial(2) → 2 × 1 = 2
factorial(3) → 3 × 2 = 6
factorial(4) → 4 × 6 = 24
This is why recursion uses more memory than a simple loop. If the recursion goes too deep — thousands or millions of levels — the call stack runs out of space. This is a stack overflow.
In competitive programming, knowing the recursion depth your solution will reach is just as important as knowing its time complexity.
A Classic Example: Fibonacci
function fib(n):
if n == 0: return 0 # base case
if n == 1: return 1 # base case
return fib(n-1) + fib(n-2) # recursive case
Each call to fib(n) spawns two more calls. This creates an expanding tree of calls that quickly becomes expensive — fib(50) would require billions of function calls in this naive form.
This is one of the most important lessons recursion teaches early:
A solution can be elegant and correct while being completely impractical for large inputs.
The fix — memoisation or dynamic programming — comes later in the series. For now, the key insight is that recursive Fibonacci repeats work because the same subproblems are solved over and over independently.
Recursion vs Iteration
Recursion and iteration often solve the same problem in fundamentally different styles. Neither is universally better — the right choice depends on the problem structure.
Aspect Recursion Iteration
─────────────────────────────────────────────────────────────────────────
Termination Stops when base case is reached Stops when loop condition is false
Memory Extra stack frame per call Typically constant extra memory
Risk Stack overflow if depth is too large Infinite loop if condition is wrong
Readability Natural for trees, divide-and-conquer Natural for simple repeated tasks
Conversion Can always be rewritten iteratively May need an explicit stack to match
Any recursive solution can be converted to an iterative one using an explicit stack data structure. However, doing so often makes the logic less readable — which is why recursion remains the preferred style for problems that are naturally tree-shaped or divide-and-conquer in nature.
Where Recursion Naturally Fits
These problem types have recursive structure built into their definition:
- Fibonacci and factorial — each value depends on smaller values of the same sequence
- Binary search — repeatedly cuts the search space in half
- Merge sort / Quick sort — sort smaller halves, then combine
- Tree traversal — visit a node, then recurse into its children
- Graph traversal (DFS) — explore a node, then recurse into its neighbours
- Dynamic programming — many DP formulations start as recursive solutions before being optimised
The common thread: the problem at size n can be expressed cleanly in terms of the same problem at size n-1 or n/2. When that structure exists, recursion is the most natural way to express it.
What Is Backtracking?
Backtracking is a systematic search strategy built on top of recursion. It explores all possible paths through a decision tree — but instead of blindly trying everything, it abandons any path the moment it becomes clear it cannot lead to a valid solution.
The pattern is always the same:
- Make a choice
- Recurse forward with that choice
- If the current path is invalid or exhausted, undo the choice
- Try the next available option
This "undo" step is what makes backtracking different from plain recursion. The algorithm is always aware of what it has done and can reverse it.
The Maze Analogy
You are navigating a maze. At each junction, you pick a direction and walk. If you hit a dead end, you retrace your steps to the last junction and try a different direction. You are not wandering randomly — you are exploring with discipline, ruling out dead ends systematically until you find the exit or confirm there isn't one.
Backtracking in Pseudocode
The general skeleton of a backtracking solution looks like this:
function backtrack(state, choices):
if is_solution(state):
record or return state
for each choice in choices:
if is_valid(choice, state):
make(choice, state) # apply the choice
backtrack(state, remaining choices)
undo(choice, state) # reverse the choice
The undo step is critical. Without it, choices from one branch of the search tree would contaminate the next branch.
Example: Generating All Binary Strings of Length n
For each position in the string, there are exactly two choices: 0 or 1. Backtracking explores all combinations:
function generate(current, n):
if length(current) == n:
print current
return
generate(current + "0", n) # try 0
generate(current + "1", n) # try 1
For n = 3, this produces:
000 001 010 011 100 101 110 111
There is no explicit "undo" step here because we are building strings by value rather than mutating a shared structure. In problems like N-Queens where you modify a board in place, the undo step becomes essential.
Classic Backtracking Problems
Backtracking is the go-to approach whenever:
- The solution is built step by step from a set of choices
- Many choices will turn out to be invalid early
- We need to find all valid configurations, or verify one exists
Classic examples:
- N-Queens — place N queens on an N×N board so none attack each other
- Sudoku solver — fill a grid such that every row, column, and box contains all digits
- Graph coloring — assign colours to nodes such that no two adjacent nodes share a colour
- Hamiltonian cycle — find a path that visits every node exactly once and returns to the start
- Subset / permutation generation — enumerate all valid combinations of a set
In all of these, the search space is too large to enumerate naively, and backtracking prunes dead-end branches before fully exploring them.
Recursion and Backtracking Together
Backtracking is almost always implemented using recursion, and for good reason. Recursion naturally models the call-and-return structure that backtracking needs:
- Each recursive call represents going deeper into the decision tree
- Returning from a call naturally represents undoing the last decision and trying the next one
- The call stack keeps track of where you are and how you got there
Recursion is the engine. Backtracking is the strategy riding it.
Key Takeaways
Recursion:
- A function that calls itself to solve smaller subproblems
- Requires a base case — without one, the program crashes
- Uses stack memory proportional to recursion depth
- Natural fit for problems with divide-and-conquer or tree structure
Backtracking:
- A systematic search that tries choices and undoes them when they fail
- Prunes invalid paths early rather than exploring the full search space
- Almost always implemented recursively
- Essential for combinatorial problems — permutations, configurations, constraint satisfaction
This series documents concepts as I learn them — follow along for each new session.