Explain this javascript function from Eloquent Javascript - Stack Overflow

admin管理员组

文章数量:1023263

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

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

• javascript

Share Improve this question Follow edited Mar 3, 2011 at 18:10 Xaisoft asked Mar 2, 2011 at 19:22 XaisoftXaisoft 46.7k8787 gold badges287287 silver badges444444 bronze badges 10

• 1 don't two pipes mean "or"? how can you return one thing OR another? – 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 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 Commented Mar 2, 2011 at 19:43
• 1 @ScottC: You should get a book. You cannot learn programming by Googling. – Lightness Races in Orbit Commented Mar 2, 2011 at 19:53
• 1 @ScottC: Sure, but be wary of many of them being incorrect/inplete/misleading. :) – Lightness Races in Orbit Commented Mar 2, 2011 at 20:08

 |  Show 5 more ments

3 Answers 3

Sorted by: Reset to default 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:

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

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

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

• javascript

Share Improve this question Follow edited Mar 3, 2011 at 18:10 Xaisoft asked Mar 2, 2011 at 19:22 XaisoftXaisoft 46.7k8787 gold badges287287 silver badges444444 bronze badges 10

• 1 don't two pipes mean "or"? how can you return one thing OR another? – 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 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 Commented Mar 2, 2011 at 19:43
• 1 @ScottC: You should get a book. You cannot learn programming by Googling. – Lightness Races in Orbit Commented Mar 2, 2011 at 19:53
• 1 @ScottC: Sure, but be wary of many of them being incorrect/inplete/misleading. :) – Lightness Races in Orbit Commented Mar 2, 2011 at 20:08

 |  Show 5 more ments

3 Answers 3

Sorted by: Reset to default 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:

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

本文标签： Explain this javascript function from Eloquent JavascriptStack Overflow