Explain this javascript function from Eloquent Javascript

I am having a hard time following this function. I do not understand how the variable start reverts back to 16 after it reaches a value of 26 which is greater than 24.

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

OK, after looking at this for sometime, I have a few questions that might clarify a few things:

1) Is it a correct statement to say that each call to find keeps track of it's own start value? For example, when find(1) is called, it's has a start value of 1, when find(1 + 5) is called, find(1)'s start value is still one, but find(1 + 5) now has it's own start value of 6.

2) I am having a hard time following the stacktrace even if I see it printed out. This is how I am viewing it:

find(1) calls find(1 + 5) //start = 1

find(6) calls find(6 + 5) // start = 6, Passes

find(11) calls find(11 + 5) // start = 11, Passes

find(16) calls find(16 + 5) // start = 16, Passes

find(21) calls find(21 + 5) // start = 21, Fails

Because find(21 + 5) returns null, it tries to call find(21 * 3) which also returns null.

This is the part I get stuck at, if both find(21 + 5) and find(21 * 3) return null, how does it know to call find(16 * 3) next. Why does it not do find(16 + 5) again?

Does it have something to do where find(21 + 5) and find(21 * 3) were called by find(16) and because those returned null into the calling function, it executed the second portion o开发者_运维百科f the || statement which was find(16 * 3).

Perhaps you're not entirely convinced, but you got it.

Regarding question 1, it's correct to say that the start values are preserved along inner calls. It's like each call has its own "context" -- even if you modify the variables and argument values, this is not carried to the outer function call. That's scope.

Question 2 seems to be related to short-circuit boolean evaluation. The behavior is exactly what you described: once the expression at left of the || operator returns something "truey", the expression at right won't be evaluated. And the contrary is true as well: if the left expression is "falsey", then the interpreter will proceed to evaluate the right expression. The resulting value will be the first non-falsey value, or the last value in the chain.

So I think you got everything covered!

I altered the original script so it prints a call trace. See it in action here.

This is a partial trace where the value of start appears to "decrease" to 16 after it goes further:

The function goes a little further under the 16 branch, then it desists, reverting back to the upper call where start is 11. Then it proceeds to try a value of 11 * 3 for start, then it desists again, and so on.

It's a different variable. start whenever a particular find(x) is called, its value of start doesn't affect any other instance of start.

when find(21) is called, it returns null, because find(26) and find(63) return null likewise, find(16) and find(11) return null

when find(6) is called, it calls find(11), which returns null, so it calls find(24) next. in the context of this call, start == 6, so it continues with start + 5 and start * 3.

find(6):
start = 6, history = (1 + 5)
     find(6 + 5):
     start = 11, history = ((1 + 5) + 5)
         find(11 + 5):
         start = 16, history = (((1 + 5) + 5) + 5)
         ... continued etc...

         find(11 * 3):
         start = 33, history = (((1 + 5) + 5) * 3)
         <end>
     find(6 * 3):
     start = 24, history = ((1 + 5) * 3)

You're not considering that the recursion branches out. It may appear that start jitters up and down, but you're just reaching the bottom of one recursion tree and skipping to a different one.

Working through the calls:

Values of start in recursion tree (branching on start+5/start*3):

                        1
              6---------+----------3
        11----+--18          8-----+-----
     16-+-33  23-+--48    13-+--24
  21-+-80   28+69       18+39 
26+63                23+90
                    28+69

See how each branch ends when the value goes too high, then the value of start that you see goes down as processing jumps to the next branch rightwards. Processing stops when the '24' is found.

(Disclaimer: I haven't fully checked all the maths, but the principle should be sound!)