# Understanding Recursion

During my Clojure training
I've found that recursion routinely trips people up. It definitely
tripped *me* up for a long time. I've tried to develop an explanation
that's clear and intuitive, so if you're still scratching your head
about recursion, read on!

A classic recursion example is calculating *n* factorial, which is *n*
multiplied by every natural number before *n*; 3 factorial is 6
(3 times 2 times 1), 4 factorial is 24, 5 factorial is 120.

The code snippet that follows is a typical implementation of factorial; if you're reading this, then presumably it's confusing - which is great! It means that I haven't written this article for nothing.

```
function factorial(n) {
if (n == 1) {
return n;
} else {
return n * factorial(n - 1);
}
}
```

What makes this function recursive is that `factorial`

calls
itself. That's also what makes the function tricky; the function calls
itself!?

We're used to functions calling *other* functions to get work
done. For example, this function uppercases a string and prepends
`"Yo, "`

to it:

```
function yoShout(str){
return "Yo, " + str.toUpperCase();
}
yoShout("gimme a donut");
// "Yo, GIMME A DONUT"
```

In this tiny example, `yoShout`

does its work by using the
`toUpperCase`

function. It's easier to understand than a recursive
function because `yoShout`

treats `toUpperCase`

as a black-box
abstraction. You don't have to tax your brain by loading
`toUpperCase`

's implementation details into your short-term memory.

Let's re-write `factorial`

to use function calls this way, with
function's body calling another function in order to get its work
done. To calculate 3 factorial, you could write a series of
functions, `factorial_1`

, `factorial_2`

, and `factorial_3`

, like this:

```
function factorial_1() {
return 1;
}
function factorial_2() {
return 2 * factorial_1();
}
function factorial_3() {
return 3 * factorial_2();
}
```

These functions feel safe and comfy. `factorial_3`

calls
`factorial_2`

, something we're completely familiar with, and likewise
`factorial_2`

calls `factorial_1`

. `factorial_3`

also does not care
how `factorial_2`

, just like in the string example.

Unfortunately, these functions are also completely impractical; can
you imagine writing `factorial_1000`

? The recursive implementation
doesn't have this problem.

My suggestion is to try seeing the recursive implementation from the same perspective as the nonrecursive imiplementation. Here's the code again:

```
function factorial(n) {
if (n == 1) {
return n;
} else {
return n * factorial(n - 1);
}
}
```

You can look at this and say, "Oh, if `n`

isn't 1, then this function
does its work by calling some black-box function named `factorial`

with the argument `n - 1`

." You can look at the call to ```
factorial(n -
1)
```

as a call to a completely different function - one that just
happens to have the same name and algorithm.

That's it! I hope it helps. If you've been confused by recursion, I'd love to hear your feedback!