×

Recursion, all the way down

So recursion is a thing. It's a very confusing thing, to be sure, but it's also a truly powerful tool, when we understand it well. The problem, for most of us, is that we don't tend to think of recursion in our day-to-day lives, but we use it, more than we realize.

It can be tricky to understand by definition. Here's what Merriam Webster says about it:

Definition of Recursion:

2: the determination of a succession of elements (such as numbers or functions) by operation on one or more preceding elements according to a rule or formula involving a finite number of steps

So we pass a series of elements into an operation, apply a rule, and then reapply that same rule to the resulting subset, to a finite limit. Clear as mud. Let's look at a concrete example of recursion, and one we do without thinking about it.

Exponents as Recursion

Remember back when, seeing a math problem that contained something like "3 to the power of 7" (often expressed on calculators as 3^7)? We don't really think about it, because in our heads we read that as: 3*3*3*3*3*3*3 (that is, three multiplied by itself seven times).

But it's recursion, in a blink. Watch.

3^7 = 3 * (3^6)
= 3 * (3 * (3^5) )
= 3 * (3 * (3 * (3^4) ) )
= 3 * (3 * (3 * (3 * (3^3) ) ) )
= 3 * (3 * (3 * (3 * (3 * (3^2) ) ) ) )
= 3 * (3 * (3 * (3 * (3 * (3 * (3^1) ) ) ) ) )
= 3 * (3 * (3 * (3 * (3 * (3 * 3) ) ) ) )
= 3 * (3 * (3 * (3 * (3 * (9) ) ) ) )
= 3 * (3 * (3 * (3 * (27) ) ) )
= 3 * (3 * (3 * (81) ) )
= 3 * (3 * (243) )
= 3 * (729)
= 2187

So what just happened? All that happens, to some degree, in our brains. We might not formalize it like that, but that's the pattern - start from the outside, simplifying the thing until we get to the innermost expression, applying the same functionality each time, then reduce that innermost expression and pass it back, one level at a time, until we have a single remaining value.

This is a great application of recursion! Speaking programmatically, we should be able to see that we can simplify that a little. Let's write an outer function that looks a LOT like what we did above - multiply our base number times an inner "recursive" call. Let's call it nthPower:

function nthPower(number, exponent){
return number * nthPower(number, exponent-1);
}

That is literally what happens each time we nest inside our 3^7 - we multiply 3 * (3^6), which is simply our number, times our number to one less exponent.

Do Not Try That At Home!

If you run that function now, you will sort of blow up your javascript engine (whether console, or a code sandbox). Why? Because we missed a crucial part of our definition up top:

Definition of Recursion:

2: the determination of a succession of elements (such as numbers or functions) by operation on one or more preceding elements according to a rule or formula involving a finite number of steps

Bold italic color added for emphasis. We missed the finite number of steps. See, the key to recursion is, at a given point, we stop looping in, and start going back OUT. At some point, we reach a condition that tells us to stop nesting, and reverse direction - we need to collapse all that nesting.

What is that point, in our case? Look back at the long block describing 3^7 - we stop going deeper when we get to this line:

= 3 * (3 * (3 * (3 * (3 * (3 * (3^1) ) ) ) ) )

That is, when our exponent is one, we have gone as deep as we need. At that point, we simply start evaluating the innermost function call (in this case, the innermost parentheses, and feed that back into the next outer function (again, in this case, the next outer parentheses:

= 3 * (3 * (3 * (3 * (3 * (3 * 3) ) ) ) )

Looking back at our nthPower function, we know we need a "stop condition", and we know that stop condition - when the exponent reaches one. Let's add that:

function nthPower(number, exponent){
if(exponent===1){
// any number to the power of one is...
//  that number. And our stop point!
return number;
} else {
// We need to keep drilling in, reducing the exponent each time.
return number * nthPower(number, exponent-1);
}
}

So here's how that function would look, in a hypothetical execution stack:

// exponent isn't 1 yet, so
nthPower(3, 7) = (3 * nthPower(3, 6) )
// Still not one, keep drilling in till it is.
nthPower(3, 7) = (3 * (3 * nthPower(3, 5) ) )
//... and keep going in until we get to
nthPower(3,7) = (3 * (3 * (3 * (3 * (3 * ( 3 * nthPower(3, 1) ) ) ) ) ) )
// At this point, the exponent is one, so we pass our number BACK
//  to the last function:
nthPower(3,7) = (3 * (3 * (3 * (3 * (3 * ( 3 * 3 ) ) ) ) ) )
// Now note, each parentheses was a function call, so we pass the inner
//  parentheses value back to the prior one each time:
nthPower(3,7) = (3 * (3 * (3 * (3 * (3 * 9 ) ) ) ) )
nthPower(3,7) = (3 * (3 * (3 * (3 * 27 ) ) ) )
nthPower(3,7) = (3 * (3 * (3 * 81 ) ) )
nthPower(3,7) = (3 * (3 * 243 ) )
nthPower(3,7) = (3 * 729 )
nthPower(3,7) = 2187

What just happened?

We started with knowing what we wanted: a number to a given exponent. We can see that this is a "recursive operation", in that the same series of steps will be applied over and over, until a certain condition is met. In our case, that condition was when the exponent is reduced to one.

We created a function that we can apply, and that can also apply itself. That is the basis of recursion - a function applies itself, over and over, eventually passing its values back out.

And, to my mind the most important bit, we examined how we think. Rather than doing the work of hard-coding our recursive process, which is often how we'll do it in our head, we looked at what the operation means, in a more abstract way. Doing so let us see how it could become "self-referencing", or recursive.

I hope this helps clear up the idea of recursion, and helps to clear up the thought process behind why recursion is a useful tool to understand. Please do comment or question, I'll be delighted to continue the conversation!

Edit: There was a question about writing this as a "fat arrow" function, using an ES6 convention and writing streamlined, minimal code. Here's that same function, doing the exact same thing, in a blink:

const nthPower = (num, exp) => exp===1? num : nthPower(num, exp-1) );

Yup. Same same same. That line says "create a function that, if exp==1, returns num and if exp !== 1, returns nthPower(num, exp-1)". This does the exact same thing as our more verbose version, in a minimal ES6 kind of way.

Developer | Tech Enthusiast | Coding Mentor

parent.tobias@gmail.com