Recursion & Backtracking

Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. Backtracking is a problem-solving strategy built on recursion that explores all possible solutions by incrementally building candidates and abandoning paths that fail.

Together, recursion and backtracking form the backbone of many algorithms involving trees, graphs, combinatorics, and search problems.

What Is Recursion?

Recursion occurs when a function solves a problem by calling itself with a simpler version of the same problem.

Every recursive algorithm must have:

1. Base case - stops the recursion
2. Recursive case - reduces the problem size

f(n) = f(n - 1)

Without a base case, recursion leads to infinite calls.

Why Recursion Works

Recursion works because:

• Large problems can be decomposed into smaller, identical problems
• Each recursive call moves closer to the base case
• The call stack keeps track of execution state automatically

This makes recursion especially natural for hierarchical structures.

Common Recursive Structures

Recursion is commonly used with:

• Trees (traversals, height, balance)
• Graphs (DFS)
• Divide-and-conquer algorithms
• Mathematical definitions (factorial, Fibonacci)

Example:

Tree
 ├── Subtree
 │    ├── Subtree
 │    └── Subtree
 └── Subtree

What Is Backtracking?

Backtracking is a systematic way of exploring choices.

It works by:

1. Choosing an option
2. Exploring recursively
3. Undoing the choice if it leads to failure

Choose → Explore → Undo

This allows algorithms to search all valid solutions efficiently.

When Backtracking Is Used

Backtracking is used when:

• Multiple choices exist at each step
• Only some choices lead to valid solutions
• All solutions or the best solution must be found

Common examples include:

• Permutations
• Combinations
• Sudoku
• N-Queens
• Maze solving

Recursion vs Backtracking

Backtracking is recursion with decision-making.

Call Stack Intuition

Each recursive call adds a frame to the call stack:

factorial(3)
 └─ factorial(2)
     └─ factorial(1)
         └─ factorial(0)

As calls return, the stack unwinds in reverse order.