Replace Loops Using Recursion Clarification

JavaScript
9

My secret sauce for understanding recursion is a little simpler: substitution. Let’s take a factorial function:

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

I hope this is familiar enough. I’m going to go ahead and turn it into an arrow function.

const fac = n => n === 1 ? 1 : n * fac(n - 1)

Now let’s do fac(5), and to do that, we need to “expand” the body of fac:

n === 1 ? 1 : n * fac(n - 1)

Substituting n with the parameter gives us:

5 === 1 ? 1 : 5 * fac(5 - 1)

We can simplify this down to:

5 * fac(4)

Now expand fac(4) the same way we did before, adding some parentheses to make it clearer:

5 * (4 === 1 ? 1 : 4 * fac(4 - 1))

Again, we can simplify it:

5 * (4 * fac(3))

Now expand and simplify fac(3). I’m just heading straight to the reduced form instead of showing the intermediate full expansion step now

5 * (4 * (3 * (fac(2)))
5 * (4 * (3 * (2 * (fac(1)))

And so on until we eventually get to:

5 * (4 * (3 * 2 * (1 === 1 ? 1 : 1 * fac(1 - 1))))

Now we see that 1 == 1, and we don’t use fac anywhere in the expansion. That’s our base case. So we get:

5 * (4 * (3 * (2 * (1))))

Or 120.

TL;DR version: when you see a function call, just substitute the whole body of the function, replacing the parameter names with their values. Keep doing this until there are no more function calls left. This works for any chain of function calls BTW, not just recursive ones, but only as long as they don’t assign to any variables (which includes changing the contents of a list).

Forget about “stacks”. Just substitute and simplify as you go.

2 Likes