To find the smallest doll you open one, and inside is the same problem: a slightly smaller doll to open, and so on. Recursion solves a task by handing a smaller copy of itself down the line until the tiniest case is trivial.
A function that calls itself
A recursive function solves a problem by calling itself on smaller inputs until it reaches a base case that stops the recursion. Divide and conquer is a recursive strategy: split a problem into independent subproblems, solve each recursively, then combine the results.
Without a base case, recursion never stops and the call stack overflows. The base case is the smallest input you can answer directly.
Merge sort splits an array in half, recursively sorts each half, and merges them — giving O(n log n) instead of O(n²).
comparing positions 0 and 1
Watch a divide-and-conquer sort split and recombine the data.
- You write factorial(n) = n × factorial(n − 1).
- Ask what stops the recursion.
- State the base case.
What you should see: The base case is factorial(0) = 1 (or factorial(1) = 1); without it the calls never terminate.