Recursion & Backtracking

A function calling itself — the key to trees, mazes, and puzzle-solving problems.

What is Recursion?

Recursion is when a function calls itself to solve smaller instances of the same problem, until it reaches a 'base case' that stops the recursion. Every recursive function needs a base case, or it will run forever (stack overflow).

int factorial(int n) {
  if (n <= 1) return 1;       // base case
  return n * factorial(n-1);  // recursive case
}

How the Call Stack Works

Each recursive call is pushed onto the call stack with its own copy of variables. When the base case is hit, calls start 'returning' and popping off the stack in reverse order — this is why deep recursion can cause a stack overflow.

What is Backtracking?

Backtracking is a technique built on recursion: try a choice, recurse forward, and if it leads to a dead end, 'backtrack' — undo that choice and try another. It's used for problems like solving a maze, N-Queens, or Sudoku, where you must explore multiple possibilities.

🌍 Real-World Use

GPS navigation apps use backtracking-like algorithms to try different routes and 'backtrack' when a route hits a dead end (like a closed road). Sudoku solver apps and chess engines exploring possible moves both rely heavily on recursion and backtracking.

💡 Pro Tip

When stuck on a recursion problem, always write the base case FIRST, then trust the recursive call to handle the smaller version correctly — this 'leap of faith' approach makes recursive thinking much easier.

🧪 Quick Self-Test

Check what you just learned — no pressure, just practice.

1. What happens if a recursive function has no base case?

2. Backtracking is best described as:

← Back to all Notes