TwiddleLab / Code / Recursion: Functions That Call Themselves

Divide and Conquer

Lesson 8 of 11 · 7 min · Free, no account needed

What you will learn

• Divide and conquer: split the problem into smaller parts, solve each part with the same function, combine the answers.
• Merge sort splits the list in half, sorts each half by trusting itself, then merges. Base case: 0 or 1 items.
• Quicksort splits around a pivot instead; binary search keeps only one half; a tournament finds the biggest.
• Decision trees in AI split data the same way: ask a question, then do the same for each part.

Start the lesson

How the lesson goes

1. You sorted by merging, bottom up. Now go top down: cut the pile in half.

   Keep cutting until nothing is left to cut.

2. Merge sort as recursion: split down, merge up.

   Step through it next to the code.

   merge_sort can't merge until both halves come back sorted, and each half waits for its own halves. So the calls go all the way down to single cards, and the merges happen on the way back up.

3. Divide and conquer.

   Divide: split the problem into smaller parts of the same kind.

   Conquer: solve each part with the same function. Trust it, like in Trust the Smaller Problem. Parts small enough are base cases.

   Combine: put the answers together. For merge sort, combining is merging two sorted halves.

4. Write merge sort in five lines.

   merge(a, b) is ready at the top. Split, sort each half, merge.

   Merging two unsorted halves gives a mess, so each half must be sorted first, by merge_sort itself. A half of the same list (merge_sort(items)) would never get smaller.

5. Quicksort by hand: split around a pivot.

   The first card of a pile is the pivot. Smaller cards go left, bigger right. Then each side, the same way.

6. Bracket: find the biggest of 16, tournament style.

   Tap the bigger number in every match. Fast and without misses.

7. AI does it too: split a pile of fruit until each pile is one kind.

   Pick a mixed pile, then a question. Each part gets the same treatment.

8. Recursive binary search: find 63.

   Each call checks the middle of what's left, then calls itself on one half. Tap the card each call checks.

   Binary search divides the list, then conquers only the half that can hold the target. There's nothing to combine, so it needs one call per level: about log2 of n calls.

9. Your merge sort, on 16 cards.

   Press Run.

Previous lesson: Drawing Fractals · Next lesson: Generate Everything: Subsets and Orders · Part of the course: Recursion: Functions That Call Themselves

Lessons are interactive and need JavaScript. Turn it on to play them.