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.