Grokking Algorithms

Chapter 4
 
 
I
 
 
Quicksort
So, for the original farm, the biggest plot size you can use is 80 × 80 m. 
To recap, here’s how D&C works:
1. Figure out a simple case as the base case.
2. Figure out how to reduce your problem and get to the base case.
D&C isn’t a simple algorithm that you can apply to a problem. Instead, 
it’s a way to think about a problem. Let’s do one more example.
You’re given an array of numbers.
You have to add up all the numbers and return the total. It’s pretty easy 
to do this with a loop:
def sum(arr):
total = 0
for x in arr:
total += x
return total
print sum([1, 2, 3, 4])
But how would you do this with a recursive function?
Step 1:
Figure out the base case. What’s the simplest array you could 
get? Think about the simplest case, and then read on. If you get an array 
with 0 or 1 element, that’s pretty easy to sum up.

---

57
Divide & conquer
So that will be the base case.
Step 2: 
You need to move closer to an empty array with every recursive 
call. How do you reduce your problem size? Here’s one way.
It’s the same as this.
In either case, the result is 12. But in the second version, you’re passing 
a smaller array into the 
sum
function. That is, 
you decreased the size of 
your problem!
Your 
sum
function could work like this.

---

58
Chapter 4
 
 
I
 
 
Quicksort
Here it is in action.
Tip
When you’re writing a recursive function involving an array, the base case is 
often an empty array or an array with one element. If you’re stuck, try that first.
Remember, recursion keeps track of the state.

---

59
Divide & conquer