Banging My Head Against Recursive Functions

In my short time studying web development, I’ve come across some tricky concepts — scope, closure, the concurrence model, etc. — but one of the hardest to wrap my head around has been recursion. I’ve spent literally hours banging my head against one recursive function or another, trying to understand what’s going on.

In this post, I’ll take a deep dive into an example provided by Marijn Haverbeke in his book Eloquent JavaScript.

Let’s get straight to it. What is recursion? A recursive function is a function that calls itself. If you didn’t know functions could that, well, they can! You can think of recursion the same way you think about loops — both repeat some code until some condition is met.

Here’s an example, also from Eloquent JavaScript:

function power(base, exponent) {
  if (exponent == 0) {
    return 1;
  } else {
    return base * power(base, exponent - 1);
  }
}

The function above will find the result of a number (the base) to the power of some other number (the exponent). I had to stare at it for a while before I understood what was going on, but it did eventually make sense. Let’s walk through it.

1. When power() is called, it first checks to see whether the exponent passed to it is 0. As some of us may remember from high school algebra, anything to the power of 0 is 1. So, if the exponent is equal to 0, power() returns 1.
2. If the exponent is anything other than 0, power() returns the base that was passed to it multiplied by another call to power().
3. The second call to power() differs from the first in one important way, namely, it decrements the exponent by 1.
4. If the second call to power(), by decreasing the exponent by 1, reduces the exponent to 0, the second call to power() will return 1 and we’re done. The return statement would resolve to base * 1. That’s unlikely to happen, as people aren’t usually interested in finding, for example, 2 to the 1st power.
5. If the exponent remains greater than 0, power() is called again. This process continues, until eventually the exponent reaches 0 and the most recent call to power() returns 1.
6. Depending on the base and exponent, the return statement will look something like base * base * ... * 1.

Imagine we’d like to know what 2 squared is. In the diagram below we can see at the top that the call to power(2,2) returns 2 * power(2, 2-1). That second call to power(2, 2-1) then returns 2 * power(2, (2-1)-1). The final call to power(2, (2-1)-1) returns 1. We’re left with the expression 2 * 2 * 1, which resolves to 4.

Although this is pretty cool, it’s not immediately obvious how this function is much of an improvement over the same function written using a for or while loop. In fact, Haverbeke points out that the recursive function above took much longer to run than a similar function he wrote with a while loop.

There are, however, times when a recursive function is a better fit than a function written with loops. Haverbeke illustrates this point with the following exercise: Write a function that determines whether a target number can be reached by starting at 1 and through a series of steps either adding 5 or multiplying by 3 at each step until the target number is reached or exceeded. If that isn’t clear yet, just bear with me. The function should return a string representing the series of operations that produces the target number, if it can be reached in this way. Otherwise, the function should return null. For example, given the target number 6, the function should return the string “(1 + 5)”. Given the target number 9, the function should return “(1 * 3) * 3” Given the target number 24, the function should return the string “((1 * 3) + 5) * 3.”

Haverbeke notes that what’s interesting about this problem is that, as the diagram below illustrates, starting from 1 and then either adding 5 or multiplying by 3, the number of possible combinations of addition and multiplication expands exponentially.

Yikes! How are we going to check all of those different possibilities to determine whether one of them produces our target number? We could probably do it with a series of FOR loops, but Haverbeke suggests that a problem like this one, in which we’d like to check each of a series of branching possibilities, is particularly well suited to a recursive solution. Here’s the solution that Haverbeke provides:

function findSolution(target) {
    function find(current, history) {
        if (current == target) {
            return history;
        } else if (current > target) {
            return null;
        } else {
            return find(current + 5, `(${history} + 5)`) ||
                   find(current * 3, `(${history} * 3)`);
        }
    }
return find(1, "1");
}
findSolution(24);

It took me a while to finally understand what was going on in this code. And I’m still a bit in awe of whoever it was who came up with the solution.

Let’s try to break it down. To reach 24, we call findSolution() with the argument 24. findSolution() then calls the function find() with arguments 1 and “1”. On first perusal, you may have been confused, as I was by the long definition of find(). It took me a moment to see that find() was actually being called at the end of findSolution(). In fact, I found it helpful to think of findSolution this way:

findSolution(target){
    function find(current, history) {...}
    find(1, "1");
}

So, where were we? Right, findSolution() calls find(1,'1'). find(1,'1') then uses an IF…ELSE IF expression to check to see whether 1 is either equal to 24 or larger than 24. After discovering that neither of those things is true, find() reaches the final ELSE expression, where it encounters the line return find(current+5, `${history}+5)`) || find(current*3, `${history}*3`).

Here’s where things get a little bit complicated. What does that line — return find(current+5, `${history}+5)`) || find(current*3, `${history}*3`) — mean? Well, an OR expression will return whichever of its sides, left or right, is resolvable to true. Note that the OR expression doesn’t necessarily return the Boolean value true or false. Rather, it returns the thing, whatever it is, that it can resolve to true. That thing could be a Boolean, a number, a string, an array, an object. How does OR decide whether something can be resolved to true? Essentially, anything that is NOT null, NaN, 0, an empty string ("" or ''), or undefined will resolve to true.

I said that OR will return whichever of its sides , left or right, is resolvable to true. Specifically, it resolves whatever is on the left side first, and if that’s resolvable to true, the OR expression returns whatever is on its left side, without even bothering to look at what’s on the right side. That’s handy. Ignoring the right side might just save you a lot of time, if what’s on the right side of the OR expression is a complicated computation.

So, find() calls the find() on the left side of the OR expression first. But, just as we saw in the case of the power() function up above, there’s one crucial difference in how find() calls itself. It alters the arguments passed in to the new call to find(). 1 becomes 1 + 5 and “1” becomes (`${history} + 5`). Don’t be confused by the `${}` notation. The string `(${history} + 5)` is just the ES6 equivalent of the ES5 string "(" + history + " + 5)".

If things were a “bit” complicated before, they’re about to get really complicated. Thus far, findSolution() has called find(), which in turn has called itself a second time. What I found it increasingly hard to do was to follow the numerous calls to find() that are required to finally reach one that either (a) returns a current number equal to our target number or (b) after exhausting all possible combinations of addition of 5 or multiplication by 3, exceeds our target number and returns null. I ended up creating a diagram, which you can see below.

Whew! I know I say this a lot, but let’s break it down.

1. At the very top of the diagram, we begin with find(1,"1"). Because 1 is neither equal to, nor larger than 24, find() calls itself.
2. We begin with the call on the left hand side of the OR statement: find(1+5, "1 +5").
3. But 6 isn’t equal to or greater than 24 either, so find() calls itself again, again starting on the left hand side: find((1+5)+5, "(1+5)+5").
4. This process continues for a while. In the diagram, I’ve numbered the calls to find(). It takes another 22 iterations for find() to reach a solution, but a lot happens on the way.
5. As you can see in the diagram, find() works its way down the left hand side of the OR statement until it reaches ((((1+5)+5)+5)+5)+5 (that’s number 6 in the diagram). This is the first time find() encounters a number greater than our target number. When find() encounters a number greater than the target number, it returns null, which resolves to false in our OR statement. So, the left hand side of our OR statement is false.
6. find() then, for the very first time, switches over to the right hand side of the OR statement, ((((1+5)+5)+5)+5)*3 (that’s number 7 in the diagram). This expression reduces to 63, which is also greater than 24, so this call to find() also returns null. null resolves to false in our OR statement. So, the right hand side of our statement is false.
7. That means that now both sides of the expression find( ((((1+5)+5)+5)+5)+5 ) || find( ((((1+5)+5)+5)+5)*3 ) have resolved to false, which in turn means that the previous call to find( (((1+5)+5)+5)+5 ) (that’s number 5 in the diagram) is also false. So, we again switch over to the right hand side of that OR statement, (((1+5)+5)+5)*3 (that’s number 8 in the diagram).
8. This entire process continues until we finally reach the 24th call to find(). That call finally satisfies the condition if(current === target) and returns our string: “((1*3)+5)*3”.

As tedious as all of that may have been, I hope that it least makes clear what was going on in this particular example. Let me know what you think in the comments.