# Recursion¶

Recursion happens when a function calls itself. You can think of it as the programming equivalent of the Droste Effect, where a picture contains a smaller version of itself.

To quote Wikipedia, “The woman in the 1904 Droste cocoa package holds two objects bearing smaller images of herself holding the same objects, and so on recursively.” This series of ever-smaller images appears to go on forever. The key word here is *appears*, because the smaller images eventually stop when they become to small to draw. This is a good thing, otherwise the artist would still be drawing it!

As a first example of recursion, I’m going to show you how to compute factorials. This pains me greatly, as it is the example that *everyone* uses, and I hate to join the crowd, but the fact is that it’s a good example for helping you wrap your head around the idea of recursion.

The factorial of an integer is represented by the exclamation mark and is the product of all the positive integers up to and including the integer in question:

```
1! = 1
2! = 2 × 1
3! = 3 × 2 × 1
4! = 4 × 3 × 2 × 1
```

and so on. You may be wondering why anyone would ever use this; it turns out to be very handy for figuring out problems involving probabilities. Now let’s add a few parentheses and reverse the order of the example, to see something interesting:

```
4! = 4 × (3 × 2 × 1) = 4 × 3!
3! = 3 × (2 × 1) = 3 × 2!
2! = 2 × (1) = 2 × 1!
1! = 1
```

Each factorial can be defined in terms of yet another factorial—until you get down to 1, which stops the process from going on forever. In general, then, *n*! can be defined as *n* × (*n* - 1)! where *n* is greater than 1. The important part is that 1! is *not* defined in terms of itself. That’s the “stopping point”; the equivalent of where the images get too small to keep drawing, and thus ending the recursion.

## Advanced Topic: Tail Recursion¶

If you were to try `(factorial 50000)`

, you would get an error: “Too much recursion.” To see why this happens, let’s look at the expression `(* n (factorial (- n 1)))`

when `n`

is 5. In order to do the multiplication, ClojureScript has to first figure out what `(factorial (- 5 1))`

works out to, so it has to “wait” until 4! is evaluated. That calculation, in turn, will have to figure out 3! before it can do *its* multiplication, so it has to wait as well, and so on. Every time this happens, the function has to store its status in an area of memory called the **stack**. That stack has limited room, and once you are out of room, you get the “too much recursion” error. This error also goes by the name *stack overflow*.

There is a way around this problem. If the recursive call is the *very last thing* in the function, then you can use the `recur`

function to say “do the recursion now,” and ClojureScript will optimize the code so that no stack space is needed for the recursion. Having the recursion as the very last thing is called **tail recursion**. (In the preceding example, the recursion isn’t the last thing that happens in the function—it’s the multiplication). To do factorials with the recursion as the very last operation, we’ll build a special helper function with two arguments. The first argument is the number whose factorial we want, and the second argument is the “result so far”:

The `factorial-helper`

function will return the result so far if `n`

is one, otherwise it will use `recur`

to recursively call itself with `(- n 1)`

and
`(* n result)`

as the arguments.

Even though the result is a number too large for ClojureScript to represent, we at least get a result rather than an error. Whenever possible, you should try to make your recursive functions tail recursive and use `recur`

so that you never have to worry about too much recursion.

## Recursion and Vectors¶

You can use recursion to process lists. For example, if you wanted to get the sum of a vector of numbers:

```
[17 4 26 3]
```

You already know how to do this with `reduce`

—`(reduce + 0 [17 4 26 3])`

, but you can think of it it as a recursive process. The sum of the entire vector is 17 plus the sum of the remainder of the vector `[4 26 3]`

. The sum of that vector is 4 plus the sum of the rest of *that* vector `[26 3]`

and so on until you get to an empty vector which means you have added everything up. In other words, recursviely defined, the sum of the entire vector is the result of adding the first element to the sum of the remaining elements.

You can use the `first`

and `rest`

functions to get the first element and remaining elements in a vector, which lets you write the recursive summation as:

The preceding example isn’t tail recursive because the addition is the last operation. We can use the helper function trick to allow the use of `recur`

:

## Strings as Collections¶

The exercise for this chapter depends on being able to manipulate strings. It turns out that you can treat a string of characters, to a large extent, as if it were a sequence of characters. Try this:

Note that `rest`

returns a sequence of characters. If you want to gather all of the items in the sequence back into a single string, you can `apply`

the `str`

function to all the characters (try it in the preceding activecode):

```
(apply str (rest s))
```

## Recursion: Palindrome tester¶

You can now use recursion to write a function named `is-palindrome?`

that takes a string as its parameter. If the string is a palindrome (it reads the same backwards and forwards), the function returns `true`

, otherwise `false`

. Thus, `(is-palindrome? "peep")`

and `(is-palindrome? "rotor")`

are `true`

while `(is-palindrome? "robber")`

is `false`

.

How can you use recursion to tell if something is a palindrome? Let’s examine *rotor*. The first and last letters match, so we discard them and are left with *oto*. Is that a palindrome? (There’s the recursion) Its first and last letters match, so we discard them and are left with *t*, which, being only one letter, is a palindrome. The same goes for *peep*. The first and last letters match, so we discard them and are left with *ee*. Again, we ask if the first and last letters match. They do, so we discard them, and we are left with nothing, which is the same backwards as forwards.

The word *robber* isn’t a palindrome: The first and last letters match, so we discard them, and are left with *obbe*. The first and last letters do **not** match, so the word isn’t a palindrome.

Here’s the logic:

If the length of the string (using

`count`

) is zero or one, we have a palindrome. This is the**end case**, which prevents infinite recursion.- Otherwise
- if the first and last letters match,
- See if everything else is a palindrome. This is where the recursion is. (Hint: use
`butlast`

and`rest`

) - otherwise it’s not a palindrome

- See if everything else is a palindrome. This is where the recursion is. (Hint: use

## A Better Palindrome Tester¶

The preceding function works fine, but it would be nice to be able to test for sentences like “A man, a plan, a canal - Panama!” or “Madam, I’m Adam.” In order to do this, you would want to convert the string to all lower case and get rid of anything that isn’t a letter. You can use `.toLowerCase`

to do the first part. Keeping only letters is a perfect job for `filter`

once you know how to test if a character is between `"a"`

and `"z"`

inclusive. You can’t do this:

```
(def ch "p")
(and (>= ch "a") (<= ch "z"))
```

because `>=`

and `<=`

expect numbers. However, you can use the `compare`

function. `compare`

returns a negative number if its first argument is less than its second argument, zero if they are equal, and positive if the first argument is greater than the second argument. Thus:

```
(compare 3 5) ; returns -1
(compare 5 5) ; returns 0
(compare 7 5) ; returns 1
(compare "a" "c") ; returns -1
(compare "x" "t") ; returns 1
```

So, you can see if a character is a letter (at least for English) with a test like this:

```
(and (>= (compare ch "a") 0) (<= (compare ch "z") 0))
```

Given this information, see if you can improve the palindrome function by converting to lower case, filtering to keep letters only, and then using the existing `is-palindrome?`

function. Hint: you can use threading `->>`

to make your code more readable.