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!