Grokking Algorithms

EXERCISES
4.1 
Write out the code for the earlier 
sum
function.
4.2 
Write a recursive function to count the number of items in a list.
4.3 
Find the maximum number in a list.
4.4
Remember binary search from chapter 1? It’s a divide-and-conquer 
algorithm, too. Can you come up with the base case and recursive 
case for binary search?
Sneak peak at functional programming
“Why would I do this recursively if I can do it easily with a loop?” you 
may be thinking. Well, this is a sneak peek into functional programming! 
Functional programming languages like Haskell don’t have loops, so 
you have to use recursion to write functions like this. If you have a good 
understanding of recursion, functional languages will be easier to learn. 
For example, here’s how you’d write a 
sum
function in Haskell:
sum [] = 0
Base case
sum (x:xs) = x + (sum xs)
Recursive case
Notice that it looks like you have two definitions for the function. The first 
definition is run when you hit the base case. The second definition runs 
at the recursive case. You can also write this function in Haskell using an 
if statement:
sum arr = if arr == []
then 0
else (head arr) + (sum (tail arr))
But the first definition is easier to read. Because Haskell makes heavy use 
of recursion, it includes all kinds of niceties like this to make recursion 
easy. If you like recursion, or you’re interested in learning a new language, 
check out Haskell.

---

60
Chapter 4
 
 
I
 
 
Quicksort
Quicksort
Quicksort is a sorting algorithm. It’s much faster than selection sort 
and is frequently used in real life. For example, the C standard library 
has a function called 
qsort
, which is its implementation of quicksort. 
Quicksort also uses D&C.
Let’s use quicksort to sort an array. What’s the simplest array that a 
sorting algorithm can handle (remember my tip from the previous 
section)? Well, some arrays don’t need to be sorted at all.
Empty arrays and arrays with just one element will be the base case. You 
can just return those arrays as is—there’s nothing to sort: