Divide and Conquer
Powerful Recursion
You've seen recursion to calculate a factorial, which "recurses" in a linear and straightforward way to 1, and you've used recursion to find a number by zigzagging in on it. These functions just called themselves once (in the body of the function), so they can be replaced with loops without much difficulty.
However, more powerful recursive techniques involve multiple recursive calls within the function itself. This lets the computer "branch out" and perform powerful calculations that could not be done with one loop alone.
Divide and Conquer
In Binary Search, the function zig-zagged until it found the desired number. Each time the function called itself, it split the size of the numbers it needed to search in half. This is an example of dividing a large problem into a smaller problem.
Challenging problems can often be solved with the Divide and Conquer approach:
- Divide the problem into smaller ones,
- Solve (or "conquer") the smaller problem.
- Combine the small solutions together to solve the entire problem.
Go on to the next page to use Divide and Conquer to solve a famous puzzle. For more practice, see the QuickSort challenges.
Challenge
You have a 1000-card deck with cards numbered from 0 to 999 that you'd like to sort. You have a small table to sort the cards on, which can hold up to 64 piles of cards. You can't stick cards in the middle of a pile, but you can split a pile into additional piles (as long as you don't go over the limit).
Can you describe out a good way to sort the entire deck of cards?
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.