A clearer explanation for recursion and flow of execution in JavaScript?

Question

I was reading Eloquent JavaScript and I came across this example for the puzzle:

Consider this puzzle: 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?

Here's the code for the solution:

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");
}

print(findSequence(24));

Could someone clear up how dod find get executed if it didn't have a value for the arguments start and goal? Also how did the recursion happen?

Answer 1

When find is called inside of findSequence, it has access to the goal variable that is set in findSequence's definition. A simple example of this is:

function outerFunction() {
  var a = 2;
  function innerFunction() {
    alert(a);
  }
  innerFunction();
}
outerFunction();

The start variable is defined when it does:

return find(1, "1");

Effectively having an initial start variable of 1, goal variable of 24, and a history of "1" on the first pass.

EDIT: Per Rob's comment, closures aren't actually what's causing this here, as find() is not being executed outside of findSequence(), scoping is causing goal to be found.

Answer 2

If I'm understanding your question correctly: The final line of code is calling findSequence(), with a goal of 24. In findSequence() there's a function called find(), which is defined and then called in the return statement for findSequence, with start equaling 1, and history equaling 1.

Answer 3

But find didn't get executed without a value for start and goal. It was first executed with the value 1 for start, and the only value for goal was 24.

Perhaps you're confused about the order of operations. There we see the declaration of a function, findSequence. During the declaration, no code is executed. The findSequence function only gets executed later, on the last line, where the result of executing the function gets printed out.

Within the declaration of findSequence, there's a declaration of another function, find. Once again, it doesn't get executed until later. The findSequence function has just one executable line of code, the one that calls find(1, "1"). Execution of that one line triggers the execution of find some number of times, recursively. The find function makes reference to goal; when the Javascript interpreter executes the code, goal always refers to the parameter of findSequence, and since in this example findSequence is only called once, goal always has the same value, 24.

You should be able to see where the recursion happened. If start was equal to goal, then the function stops; it returns the history of how it arrived at that number. If start is greater than goal, then it returns null, indicating that that path was not a path to the target number. If start is still less than goal, then the function tries calling itself with its start value plus 5. If that returns a non-null value, then that's what gets returned. Otherwise, it tries multiplying by 3 and returning that history value instead.

Note that although this code can return many numbers, it cannot return all numbers. If the goal is 2, for example, findSequence will return null because there is no way to start at 1 and get to 2 by adding 5 or multiplying by 3.