This post covers Chapter 3 from Grokking Algorithms, which focuses on recursion.

Recursion

Recursion is an unique concept. It’s similar to looping in that you iterate through a collection of items. It’s different in that each iteration depends on the result of all subsequent iterations.

A good analogy to recursion is a set of Russian nesting dolls. You start with all of the dolls unnested in a line and your goal is to nest them. You open the largest doll in order to fill it, but to do so, you need the second largest doll. You can’t nest that doll yet because you need to open it and nest the third largest doll inside it, and so on.

You move down the line until you reach the smallest doll, which doesn’t open. This last doll represents the base case, since it doesn’t recur any further. All the other dolls represent the recursive case.

You take the last doll and nest it in the slightly larger doll and move back up the line. Each doll is only complete when all of the smaller dolls have been nested inside it.

Tail-Call Optimization

Putting aside the nesting doll analogy, when your code is in a recursive loop, any local values from the current iteration are pushed onto the stack when you recur to be available when you return from recurring down further iterations. If you have a large number of iterations, your stack will grow very large as well.

If recurring is the last thing your program does in a particular iteration, you don’t need to save any local variables, since they are not needed anymore. Because of this, your program only needs to save values from a single iteration (the current iteration) onto the stack at a time, using constant stack space.

Some languages provide what’s called tail-call optimization, which automatically detects when recursion happens in the tail position of your code and optimizes stack usage by overwriting the current iteration’s frame on the stack with the values from the next iteration instead of pushing an additional frame onto the stack.

Clojure unfortunately does not provide tail-call optimization, but instead provides the recur special form, which you use like a function.

The recur Special Form

If recursion happens at the end of your loop or function, you can use the recur special form so your program uses constant stack space.

In a loop, calling recur is the only way to iterate again. In a function, this is the preferred way over calling the function again by its name, as the latter approach could take up large amounts of stack space for unbounded loops.

But again, you can only use recur in the tail position. In fact, the Clojure compiler validates that the recur call is in the tail position of your loop or function and will throw an error if this is not the case.

Now let’s implement the programs from this chapter in Clojure.

Countdown

For countdown, our recursive case is encountered when the condition to the when is true. In that case, we recur with i - 1. The base case is implicit, since the body of when will not run if the condition is false.

(defn countdown
  [i]
  (println i)
  (when (> i 1)
    (recur (dec i))))

Here is the output if we call countdown with 5:

(countdown 5)

5
4
3
2
1

Greet

The greet example is not recursive, but is used to demonstrate how the call stack works.

Here it is in Clojure:

(defn- greet2
  [name]
  (println (str "how are you, " name "?")))

(defn- bye []
  (println "ok bye!"))

(defn greet
  [name]
  (println (str "hello, " name "!"))
  (greet2 name)
  (println "getting ready to say bye...")
  (bye))

And here is the output if we call it with "John":

(greet "John")

hello, John!
how are you, John?
getting ready to say bye...
ok bye!

Factorial

Finally, here is the solution for the factorial example:

(defn fact
  [x]
  (if (<= x 1)
    1
    (* x (fact (dec x)))))

The base case is if x is less than or equal to 1, which returns 1 for 1 or 0 (or anything less), while the recursive case multiplies x by the result of calling fact with x-1.

If you notice, I used fact instead of recur to recur. The reason is because in order to evaluate the expression (* x (fact (dec x))), we need to first evaluate (fact (dec x)). And in order to evaluate that, we have to push the new value (dec x) onto the stack while keeping the existing value of x on the stack as well.

In other words, we have hold onto the current nesting doll until we get back all the smaller dolls, nested.

Here is the output if we call fact with 5:

(fact 5)

120

Key Takeaways

• Recursive programs have a base case (return) and a recursive case (recur).
• The recur special form can be called from the tail position to conserve stack space.
• Clojure’s loop provides iteration through recursion.