Course contentsShow
← Computer Science
Lesson 866 of 2,87220. Recursion Patterns and TechniquesFree lesson

Problem Decomposition in Recursion

Learn to break complex problems into smaller self-similar subproblems that can be solved recursively.

Problem Decomposition in Recursion

You'll learn how to break down complex problems into smaller, self-similar pieces that recursion can naturally solve.

When you face a seemingly overwhelming recursive problem, the key skill is decomposition—identifying how the problem can be split into smaller versions of itself. Each smaller version should be structurally similar to the original, just with reduced input or scope.

The Core Idea

Think of problem decomposition like Russian nesting dolls. The outer doll contains progressively smaller dolls, each identical in shape but different in size. Similarly, a recursive problem contains smaller instances of the same problem type.

The decomposition checklist:

  1. Identify the self-similarity — How does a smaller version of the problem relate to the larger one?
  2. Define the reduction — What parameter(s) shrink with each recursive call?
  3. Establish the base case — When is the problem so small it's trivial to solve?
  4. Combine results — How do solutions to subproblems build the final answer?

Examples You've Seen

  • N-Queens: Place one queen, then recursively solve N-1 Queens on the remaining rows
  • Sudoku Solver: Fill one cell, recursively solve the remaining empty cells
  • Generating Permutations: Fix one element, recursively permute the rest
  • Mergesort: Split array in half, recursively sort each half, merge results
  • Backtracking in general: Make one choice, recursively explore remaining choices

The pattern is consistent: solve "one step" or "one piece," then trust recursion to handle what remains.

Why It Matters

Problem decomposition transforms intimidating challenges into manageable steps. Instead of seeing the entire mountain, you focus on one foothold at a time, knowing the same strategy works for each step ahead.

Key Takeaway: Effective recursion comes from recognizing how a problem naturally divides into smaller self-similar subproblems—identify what shrinks, what stays the same, and when to stop.