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.^{1}

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?

- It’s usually easier to reason about the base case than recursive cases.
- Once you have the base case, it’s easier to reason about recursive cases.
- 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.

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

## Leave a Reply