DSA: Recursion and Backtracking
Understand how recursive thinking and backtracking power solutions to complex combinatorial problems.
Recursion Basics
Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive solution must have a base case to stop and a recursive case to reduce the problem.
Base Case and Recursive Case
A recursive function must answer two questions: when do we stop, and how do we reduce the problem?
- Base case: the simplest input where the answer is known directly (no further call needed)
- Recursive case: the function calls itself with a smaller or simpler argument
- Missing base case causes infinite recursion and stack overflow
- Each call adds a new frame to the call stack with its own local variables
Factorial Using Recursion
C++factorial(5) calls factorial(4), which calls factorial(3), down to factorial(0) which returns 1.
Direct vs Indirect Recursion
In direct recursion a function calls itself. In indirect recursion, function A calls function B, which calls function A again, forming a cycle.
Types of Recursion
Most problems use direct recursion. Indirect recursion appears in mutual recursion patterns like even/odd checks.
- Direct: f() calls f(), the most common form
- Indirect: f() calls g(), and g() calls f(), both need a shared base case
- Both types share the same call-stack mechanics
- Indirect recursion can make the termination condition harder to spot
Indirect Recursion: Even and Odd
C++isEven and isOdd call each other, converging toward n=0 as the shared base case.
Tail Recursion and Optimization
A function is tail-recursive when the recursive call is the very last operation, nothing is done with its return value except returning it. Compilers can optimize this to reuse the same stack frame.
Tail Recursion
Move all computation before the recursive call so the function returns immediately after the call.
- Non-tail: result = n * factorial(n-1), must wait for the call to multiply
- Tail: pass the accumulator as a parameter so nothing is pending after the call
- Tail-call optimization (TCO) converts the recursion to a loop internally
- Prevents stack overflow on very deep call chains when TCO is applied
Tail-Recursive Factorial
C++The accumulator carries the product forward. No multiplication is pending after the recursive call.
Recursion Tree and Call Stack
Drawing the recursion tree shows how many times a function is called and helps calculate time complexity. The call stack shows which frames are alive simultaneously.
Fibonacci Recursion Tree
Naive Fibonacci has an exponential recursion tree because fib(n-2) sub-problems overlap with fib(n-1) sub-problems.
- fib(5) spawns fib(4) and fib(3); fib(4) spawns fib(3) and fib(2), fib(3) is computed twice
- Total calls for fib(n) grows as O(2ⁿ) without memoization
- Max call stack depth at any moment equals n (the tree height)
- Overlapping sub-problems make this ideal for dynamic programming (memoization)
Fibonacci: Naive Recursion
C++Simple but exponential. fib(40) requires over a billion calls without memoization.
Tower of Hanoi
Tower of Hanoi is a classic recursion problem: move n disks from a source peg to a destination peg using an auxiliary peg, never placing a larger disk on a smaller one.
Tower of Hanoi Strategy
Solve for n disks by reducing to two problems of n-1 disks: move the top n-1 disks out of the way, move the bottom disk, then bring the n-1 disks back.
- Step 1: move n-1 disks from source to auxiliary using destination
- Step 2: move the largest disk from source to destination
- Step 3: move n-1 disks from auxiliary to destination using source
- Total moves: 2ⁿ - 1 (minimum possible)
Tower of Hanoi (3 Disks)
C++3 disks require 7 moves (2³-1). The recursion naturally produces the optimal sequence.
Backtracking Fundamentals
Backtracking is a refined brute-force technique: make a choice, recurse to explore that path, and if it leads to a dead end, undo the choice and try the next option.
Backtracking Pattern
The three-step template: choose, explore, unchoose. The unchoose step is what separates backtracking from plain recursion.
- Choose: pick an option from the available candidates
- Explore: recurse with that choice applied to the state
- Unchoose: undo the choice so the state is clean for the next candidate
- A constraint check before recursing prunes invalid branches early (pruning)
All Permutations of a String
C++swap-recurse-swap is the classic backtracking template. Each call fixes one position and recurses on the rest.
Subset Generation
Every element has two choices at each recursive step: include it in the current subset or skip it. This produces all 2ⁿ subsets of a set.
Subset Enumeration
At each index, branch into two paths: include the element and recurse, or skip it and recurse.
- A set of n elements has exactly 2ⁿ subsets (including the empty set)
- Time: O(2ⁿ), Space: O(n) for the recursion stack
- The include/exclude pattern also generates power sets and combination sums
- Adding a constraint (e.g. sum = target) is all that is needed to solve subset-sum problems
All Subsets of {1, 2, 3}
C++Each element is either included (push then recurse) or excluded (pop then recurse), producing 2³ = 8 subsets.
N-Queens Problem
Place N chess queens on an N×N board so that no two queens share the same row, column, or diagonal. Backtracking tries each column in the current row and prunes when a conflict is detected.
N-Queens Backtracking
Place one queen per row. Before placing, verify no previously placed queen attacks this position. If a valid column exists, recurse to the next row; otherwise backtrack.
- One queen per row: iterate columns in the current row
- Conflict check: same column, or |row diff| = |col diff| for diagonals
- If all N rows are filled successfully, count or print the solution
- For an 8×8 board there are 92 distinct solutions
N-Queens: Count All Solutions
C++board[row] stores the column of the queen in that row. isSafe checks column and diagonal conflicts.
Rat in a Maze
A rat starts at the top-left of a grid and must reach the bottom-right. Cells marked 1 are open; cells marked 0 are blocked. Backtracking explores all possible paths.
Maze Path Finder
Mark the current cell as visited before recursing and unmark it when backtracking so other paths can use it.
- Valid move: within bounds, cell value is 1, cell not already visited
- Mark visited cells with 0 before recursing; restore to 1 when backtracking
- Move in four directions: down, right, up, left
- Time complexity: O(4^(n²)) in the worst case without pruning
Rat in a Maze (3×3)
C++Marking cells 0 before recursing prevents revisiting. Restoring to 1 on backtrack keeps other paths valid.
Sudoku Solver
Backtracking solves Sudoku by placing digits 1–9 in empty cells, checking row, column, and 3×3 box constraints before recursing. If no digit fits, it backtracks.
Sudoku Backtracking
Find the next empty cell, try digits 1–9, validate each, recurse if valid, and undo on failure.
- Scan rows first to find an empty cell (value = 0)
- For each candidate digit, check the row, column, and 3×3 box
- Place the digit and recurse; if recursion returns false, reset the cell to 0
- Return true when no empty cell remains (board is solved)
Sudoku Solver via Backtracking
C++isValid checks all three constraints in one loop using box indexing: 3*(r/3)+i/3, 3*(c/3)+i%3.
Knowledge Check
1. What is the base case in recursion?
2. What happens if a recursive function has no base case?
3. Tail recursion is preferred because:
4. In Tower of Hanoi with n disks, how many moves are required?
5. What does backtracking do when it reaches a dead end?
6. Which of these is NOT a classic backtracking problem?
7. How many subsets does a set of n elements have?
8. The call stack in recursion stores: