Thanks to Eric Grimson for this idea.

When you’re writing a recursive function…

Write the base case first.

That’s where it returns a value, instead of recursing.

To show this, let’s write a factorial function.

A factorial is a “product of all positive integers less than or equal to n,” according to Wikipedia.

The factorial of 7 is 7 * 6 * 5 * 4 * 3 * 2 * 1.

Let’s recurse from top to bottom, though you could also recurse from bottom to top.

So (factorial 7) will recurse from 7 to 6 to 5, etc…

What’s the base case for this function?

Because factorial computes non-negative values…

Once you get to 1, it’s fine to return that.

That’s the base case:

(defn factorial [n]
  (if (= n 1)
    1 ;; Base case
    "not implemented"))
Code language: Clojure (clojure)

But it’s a little more complicated, as (factorial 0) should also return 1:

(defn factorial [n]
  (if (<= n 1)
    1
    "not implemented"))
Code language: Clojure (clojure)

Now that we have the base case…

We only have to think about the case 1 level above it.

The lowest base case was (factorial 1), so 1 level above it is (factorial 2).

(factorial 2) is 2 times the base case.

On line 4, we’ll return 2 times the base case:

(defn factorial [n]
  (if (<= n 1)
    1
    (* 2 (factorial (- n 1)))))
Code language: Clojure (clojure)

Of course, this function is too naïve, as it won’t compute (factorial 3).

Let’s make it compute that by changing 2 to n

(defn factorial [n]
  (if (<= n 1)
    1
    (* n (factorial (- n 1)))))
Code language: Clojure (clojure)

This function is now complete.

case	argument	final return
base	0	1
base	1	1
recursive	2	2
recursive	3	6
recursive	4	24
recursive	5	120

Let’s do another example.

The previous factorial function didn’t do tail recursion.

So every recursive call adds to the stack.

The factorial function below will use “linear iterative” recursion, like in Structure and Interpretation of Computer Programs.

Similar to this in JavaScript:

function factorial(n) {
  let product = 1;
  for (let i = n; i >= 1; i--) {
    product = product * i
  }
  return product;
}Code language: JavaScript (javascript)

To do that in Clojure, we’ll use a helper function factorial-iter, like in Structure and Interpretation of Computer Programs.

(defn factorial-iter 
  "Helper function for factorial"
  [product i]
  "not implemented")

(defn factorial [n]
  (factorial-iter n (- n 1)))Code language: Clojure (clojure)

The factorial-iter function will be like the JavaScript for loop above.

We’ll start with the base case again.¹

The i parameter keeps track of the iteration, like the i in the JavaScript for loop above.

So when i is 1 or 0, we should return product:

(defn factorial-iter [product i]
  (if
    (<= i 1)
      product ;; Base case
      "not implemented")))
Code language: Clojure (clojure)

Then, we’ll implement the recursive case:

(defn factorial-iter [product i]
  (if
    (<= i 1)
      product
      (recur (* product i) (- i 1))))
Code language: Clojure (clojure)

The fact that it calls recur on line 5 means it does tail call optimization.

The call stack doesn’t get bigger for every recursive call.

Why start with the base case?

1. It’s usually easier to reason about the base case than recursive cases.
2. Once you have the base case, it’s easier to reason about recursive cases.
3. You can test the function if you only have the base case. Even the most basic example above works, though only for (factorial 1):

(defn factorial [n]
  (if (= n 1)
    1 ;; Base case
    "not implemented"))Code language: Clojure (clojure)

It sounds backwards.

But this makes it easier to write recursive functions.

• Twitter
• Reddit
• Mail

1. The loop form in Clojure removes the need for this helper function. [↩]