2026

Recursion & Backtracking

Backtracking / Complete Search

1. Any permutation or combination problem is essentially a recursion/backtracking problem because you need to explore all possible choices and select the ones that satisfy some condition.

   Backtracking often involves:

   • making a choice,
   • exploring further,
   • undoing the choice if it doesn't work.

   More accurately, backtracking is about keeping track of decisions and reverting them when necessary.

   Classic example:

   • N Queens / Chessboard problems

2. If you want to do a complete search (for example generating all subsets), there are usually two common approaches:

   • Exploit the bit representation of integers
   • Use recursive search / backtracking

Example:

subsets([1,2,3])

[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

3. Pruning and Meet in the Middle are optimization techniques used with recursive search.

4. Pruning means cutting off a branch of the search tree early because it cannot possibly lead to a valid or optimal solution.

Instead of exploring useless states, you stop immediately.

Example:

• In N Queens, if two queens already attack each other, there is no point exploring further placements.

5. A backtracking algorithm usually:
   • starts with an empty solution,
   • extends the solution step by step,
   • recursively explores all possibilities,
   • backtracks when a path becomes invalid.

Generic structure:

void search(...) {
    if(valid solution) {
        process solution;
        return;
    }

    for(all possible choices) {
        make choice;
        search(...);
        undo choice;
    }
}

Note

Linked Lists are often manipulated recursively because the recursive structure naturally matches the node-next-node definition.

Thinking Recursively

The Recursive Leap of Faith

The most important thing in recursion is:

Trust your function.

Trying to mentally track every recursive call quickly becomes messy:

• "This calls that..."
• "Then this condition runs..."
• "Then another recursive call..."
• "Then we return here..."

This becomes extremely difficult to dry run mentally before writing the full solution.

Instead:

• Solve the smaller problem correctly.
• Trust that the recursive function will also solve the larger version similarly.

This idea is essentially:

Mathematical Induction.

Important Rules

1. Have a Base Case

Without a base case, recursion never stops.

2. Define the Smaller Problem Clearly

Your recursive function should reduce the problem size.

3. Trust the Function

Do not try to manually track every level of recursion.

Think of recursion like a black box:

"If this smaller problem gets solved correctly, then I can build the larger answer from it."

Examples

Fibonacci

fibo(n) = fibo(n - 1) + fibo(n - 2)

Here you're trusting that:

• fibo(n - 1) is already computed correctly
• fibo(n - 2) is already computed correctly

You simply combine them.

Sum of Digits

sum_dig(n) = sum_dig(remaining_digits) + last_digit

Example:

12143
1214 + 3
121 + 4
12 + 1
1 + 2
0 + 1

At every step:

• remove the last digit,
• trust recursion to compute the smaller answer,
• add the current digit.

Final Intuition

Recursion is less about "tracking execution" and more about:

• defining the problem elegantly,
• reducing it into smaller versions,
• and trusting the recursive structure.

Backtracking is recursion with decision making:

• choose,
• explore,
• undo,
• repeat.