This post covers Chapter 4 from Grokking Algorithms, which introduces the Divide and Conquer approach as a lead-in to the Quicksort algorithm.

Divide and Conquer

When I was ten years old, I participated in a weeklong camp program as part of my fifth grade class. The participants were divided into groups, with each group assigned a guide. One night, our guide told a fable about a village in ancient times. The people of the village were going through a difficult time and needed to appoint a leader to help them through it.

So the wise men of the village set out a challenge. Whoever could break a bundle of sticks with their bare hands would become the leader. So one-by-one, ambitious villagers stepped up, hoping to become the leader of the village. And one-by-one, they all failed to break the bundle of sticks, no matter how strong they were or how hard they tried.

Finally, a meek villager walked up to the bundle of sticks and untied the twine from each end and began breaking the sticks one-by-one. When he was finished, the wise men declared him the leader of the village.

The point of the story is that when we’re faced with a daunting problem, it’s often best to break it up into small pieces and tackle each piece one at a time.

Farm Plot

The farm plot problem presented in the book boils down to finding the greatest common denominator of two numbers. The order of the inputs, width and length, is irrelevant to the output.

Let’s start by defining a function that takes in two dimensions, both at least 0. Since the order doesn’t matter, we’ll just call our arguments dim-1 and dim-2.

(defn gcd
  [dim-1 dim-2]
  {:pre [(>= dim-1 0)
         (>= dim-2 0)]}
  )

We’ll need to know which of the inputs is the smaller value and which is the larger value, so let’s take care of that.

(defn gcd
  [dim-1 dim-2]
  {:pre [(>= dim-1 0)
         (>= dim-2 0)]}
  (let [[smaller larger] (sort [dim-1 dim-2])]
    )
  )

Now, let’s define our base case and our recursive case.

Base case:

• smaller = 0, return larger
• larger = 0, return smaller
• the remainder of larger/smaller = 0, return smaller

For our recursive case, we recur with smaller as one dimension and the remainder of larger/smaller as the other.

(defn gcd
  [dim-1 dim-2]
  {:pre [(>= dim-1 0)
         (>= dim-2 0)]}
  (let [[smaller larger] (sort [dim-1 dim-2])]
    (cond
      (= 0 smaller)              larger
      (= 0 (mod larger smaller)) smaller
      :else                      (recur smaller (mod larger smaller)))))

The second condition in our cond covers both the case when larger equals 0 and the case when the remainder of larger/smaller equals 0, since 0 divided by any number has a remainder of 0.

Our code works as is, but the expression (mod larger smaller) is repeated twice. Let’s extract it into a variable.

(defn gcd
  [dim-1 dim-2]
  {:pre [(>= dim-1 0)
         (>= dim-2 0)]}
  (let [[smaller larger] (sort [dim-1 dim-2])
        remainder        (delay (mod larger smaller))]
    (cond
      (= 0 smaller)    larger
      (= 0 @remainder) smaller
      :else            (recur smaller @remainder))))

We extracted the result of the mod operation into a local variable called remainder. The problem is that mod needs to do a division operation to resolve. If the divisor, smaller in our case, is 0, our code will throw a divide by zero error.

So we need to delay the execution of that mod operation until after we’ve verified that smaller is not equal to 0. When we wrap an expression in delay, it doesn’t get executed until the first time we dereference it with @. Subsequent dereferences use the cached value that was previously calculated.

In this case, remainder is calculated for the first time in the second to last line and its cached value is used in the last line.

Sum

Loop

Clojure, like many other functional languages, implements looping using recursion behind the scenes. So there’s technically no way to loop in Clojure without using recursion.

So for the loop version of sum, we’ll use an approach that doesn’t require us to explicitly write recursive code. The reduce function works well here.

(defn sum
  [nums]
  (reduce + nums))

Recursive

And here is the recursive version of sum.

Base case:

• nums contains 0 elements, return 0
• nums contains 1 element, return the element

Recursive case:

• nums contains 2 or more elements, add the first number to the sum of all the other numbers

(defn sum
  [nums]
  (case (count nums)
    0 0
    1 (first nums)
    (+ (first nums)
       (sum (rest nums)))))

Count

Base case:

• empty collection, return 0

Recursive case:

• non-empty collection, increment the count and recur with all but the first item in the collection

Implementing a count function using recursion looks like this:

(defn count-r
  [nums]
  (if (empty? nums)
    0
    (inc (count-r (rest nums)))))

Max

Base case:

• 0 elements in collection, return nil
• 1 element in collection, return the element

Recursive case:

• two or more elements, return the max between the and the max of the rest

Implementing a maximum function with recursion looks like this:

(defn max-r
  [nums]
  (if (<= (count nums) 1)
    (first nums)
    (let [max-sub (max-r (rest nums))]
      (if (> (first nums) max-sub)
        (first nums)
        max-sub))))

Both scenarios in our base case are handled by (first nums), since calling first on an empty collection returns nil, while calling it on a collection with a single element returns that element.

In our recursive case, we first calculate the maximum of all but the first element in nums, and compare that value with first element.

Quicksort

Base case:

• 0 elements in the collection, return the collection
• 1 element in the list, return the collection

For our recursive case, in which our collection contains two or more elements, we select a pivot value. We’ll use the pivot to divide our collection into three parts:

• Sorted values less than (or equal to) the pivot
• The pivot
• Sorted values greater than the pivot

(defn qsort
  [nums]
  (if (< (count nums) 2)
    nums
    (let [[pivot & rest] nums
          less    (filter #(<= % pivot) rest)
          greater (filter #(> % pivot) rest)]
      (concat (qsort less)
              [pivot]
              (qsort greater)))))

We arbitrarily select the first element in nums as the pivot value and recur over less and greater to sort those sub collections.

Key Takeaways

• Divide and conquer is a general strategy, which involves breaking a problem down to the most basic unit.
• Quicksort is divide and conquer applied to sorting.