How does this recursion work?

Question

This is an example from Eloquent Javascript:

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of additions and multiplications that produce that number?

I'm having trouble understanding how the recursion is working here, wondering if someone could write out a couple times how find is getting called or some other explanation.

function findSequence(goal) {
  function find(start, history) {
    if (start == goal)
      return history;
    else if (start > goal)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3)

Answer 1

The function runs a rather simple brute force search with backtracking: at each invocation level it tries adding 5 to the number, and see if starting from the resultant number gets you to the goal. If it does, the result is returned; otherwise, the number is multiplied by 3, and the search for the goal continues from that new number. As the recursion goes along, the textual representation of the expression producing the number is passed to the next invocation levels.

The search for 14 goes as follows:

(1,  "1")
(5,  "1+5")
(10, "(1+5)+5")
(15, "((1+5)+5)+5") <<= Fail
(30, "((1+5)+5)*3") <<= Fail
(15, "(1+5)*3") <<= Fail
(3,  "1*3")
(8,  "(1*3)+5")
(13, "((1*3)+5)+5")
(18, "(((1*3)+5)+5)+5") <<= Fail
(39, "(((1*3)+5)+5)*3") <<= Fail
(24,  "((1*3)+5)*3") <<= Fail
(9, "(1*3)*3")
(14, "((1*3)*3)+5) <<= Success!

Answer 2

This function starts with 1 and then tries to either add 5 to it or multiply it by 3. If that is equal to the goal, the function terminates and prints out the expression found. If not, it calls itself recursively with the value at that level until a match is found or until the values become too high.

Does that help?

Answer 3

someone could write out a couple times how find is getting called.

Here you go:

find(1, "1") -> find(3, "(1 * 3)")
             -> find(8, "((1 * 3) + 5)")
             -> find(24, "(((1 * 3) + 5) * 3)")

Answer 4

The body of find has three exit paths, two that correspond to a condition that stops the recursion and one that recurses:

if (start == goal)
  return history; // stop recursion: solution found
else if (start > goal)
  return null;    // stop recursion: solution impossible
else
  // ...

The third path is actually a "branch", in that it recurses twice (once to try the addition, once for the multiplication):

  return find(start + 5, "(" + history + " + 5)") ||
         find(start * 3, "(" + history + " * 3)");

So what's going on here?

First of all, note that each of these two find calls will evaluate to either a non-empty string (the history of operations) or to null. Since a non-empty string is a "truthy" value and null is a "falsy" value, we take advantage of this by joining them with the || operator; this operator evaluates to its first operand if it is truthy, otherwise to the second operand.

This means that the first recursion branch (+5) will be evaluated first. If there is a sequence of operations that starts by adding 5 and reaches the goal then the description of this sequence will be returned. Otherwise, if there is a sequence that starts by multiplying by 3 and reaches the goal the description of that history will be returned.

If there is no way to reach the goal then the return value will be the null produced by the second branch.

Answer 5

If you get rid of the pretty printing stuff, the code is a little easier to read:

function findSequence(goal) {
    function find(start) {
        if (start == goal) {
            return true;
        } else if (start > goal) {
            return false;
        } else {
            return find(start + 5) || find(start * 3);
        }
    }

    return find(1);
}

The outer function, findSequence, dynamically creates a new function called find where goal is taken from the scope of the parent function. You could re-write it like this for clarity:

function findSequence(start, goal) {
    if (start == goal) {
        return true;
    } else if (start > goal) {
        return false;
    } else {
        return findSequence(start + 5, goal) || findSequence(start * 3, goal);
    }
}

Now, you can see a little more clearly what happens. The recursive step is in the final return statement, which tries both start + 5 and start * 3 at each step and picks the branch that eventually returns true.

Follow the logic of findSequence(1, 23) by hand and you'll understand how it works.

Answer 6

The best way for you to learn this would be to trace through the code in the JavaScript debugger.

Have you used the debugger before? It's really fun and enlightening and easy too.

Simply add a debugger; statement where you want the code to stop. A good place would be just before you call findSequence():

debugger;
console.log(findSequence(24));

Now load your page in Chrome with the Developer Tools open. Your code will stop on that debugger; line. Find the button that lets you Step Into your code (over on the right above the Watch Expressions panel). Click that button to step into the findSequence() call. Each time you click it, it will step into the next line of code, which includes going into each recursive call.

Whenever the code is stopped, you can hover the mouse over any variable to view it, or look at the variables in the panel on the right. There is also a Call Stack that will show you exactly where you are in the recursive calls.

I'm sure somebody could explain the recursion to you, but you will learn a lot more if you actually experience it by stepping through your code in the debugger.