Explain this javascript function from Eloquent Javascript

Question

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 of the || statement which was find(16 * 3).

don't two pipes mean "or"? how can you return one thing OR another? — ScottC
– ScottC, Commented Mar 2, 2011 at 19:37
@ScottC: in Javascript, "OR" || returns the first item if it is true-ish, or the second item if the first item is false-ish (which includes null). It's a generalization of the boolean-or, and behaves similarly to a null-coalesce operator. — Jimmy
– Jimmy, Commented Mar 2, 2011 at 19:41
@ScottC: Read the chapter in your Javascript book about boolean conditions. It's the same as var x = y || z; return x;. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Mar 2, 2011 at 19:43
@ScottC: You should get a book. You cannot learn programming by Googling. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Mar 2, 2011 at 19:53
@ScottC: Sure, but be wary of many of them being incorrect/incomplete/misleading. :) — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Mar 2, 2011 at 20:08

Humberto · Accepted Answer · 2011-03-04 18:33:49Z

6

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:

enter image description here

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.

edited Mar 4, 2011 at 18:33

answered Mar 2, 2011 at 20:58

Humberto

7,1994 gold badges33 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Xaisoft Over a year ago

Awesome, I am walking through it by hand and will probably update my question because I think I am getting it, but not quite yet.

Jimmy · Accepted Answer · 2011-03-02 19:37:14Z

2

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)

answered Mar 2, 2011 at 19:37

Jimmy

91.9k19 gold badges123 silver badges139 bronze badges

2 Comments

ScottC Over a year ago

I agree, the new instances of find contain new instances of start and history, maybe instead of passing the variable ByVal javascript has a way of passing ByRef?? like c++? if that is infact what you are trying to accomplish

Jimmy Over a year ago

well, the stated function is correct. Xaisoft just seems to think there is a single context of find (there are multiple). Compare with "there is a single context of findSequence, and thus a single value for goal" (which is true)

Lightness Races in Orbit · Accepted Answer · 2011-03-02 19:51:01Z

2

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

edited Mar 2, 2011 at 19:51

answered Mar 2, 2011 at 19:43

Lightness Races in Orbit

387k77 gold badges670 silver badges1.1k bronze badges

5 Comments

Jimmy Over a year ago

it's a depth-first search stopping when start > goal, so find(26) does happen before find(24) occurs, which is what Xaisoft is confused about.

Lightness Races in Orbit Over a year ago

@Jimmy: It doesn't stop when start > goal, it stops when start == goal. When start > goal the current tree is abandoned, but others are still searched.

Jimmy Over a year ago

yes, the confusion in the question is because he thinks there's only one value of start.

Lightness Races in Orbit Over a year ago

@Jimmy: Yep, and I have demonstrated how the value he's seeing -- presumably in a "watch" window -- can safely change up and down up and down, as the stack tree is swept.

Jimmy Over a year ago

oh, good call about the "watch" window. Sometimes I wonder how people make this misunderstanding.

Collectives™ on Stack Overflow

Explain this javascript function from Eloquent Javascript

3 Answers 3

1 Comment

2 Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related