1

This particular puzzle from Eloquent JavaScript has been asked elsewhere on SO, but I haven't found one that relates to the specific question I have in reference to it.

function findSolution(target) {
  function find(start, history) {
    if (start == target)
      return history;
    else if (start > target)
      return null;
    else
      return find(start + 5, `(${history} + 5)`) ||
             find(start * 3, `(${history} * 3)`);
  }
  return find(1, "1");
}

console.log(findSolution(13));
// (((1 * 3) + 5) +5)

... and here's the call stack:

find(1, "1")
  find(6, "(1 + 5)")
    find(11, "((1 + 5) + 5)")
      find(16, "(((1 + 5) + 5) + 5)")
        too big
      find(33, "(((1 + 5) + 5) * 3)")
        too big
    find(18, "((1 + 5) * 3)")
      too big
  find(3, "(1 * 3)")
    find(8, "((1 * 3) + 5)")
      find(13, "(((1 * 3) + 5) + 5)")
        found!

My question pertains to how return null; works here. I'd like to better understand how this statement results in find() working back down the previously calculated target parameters; e.g., find(33, .. --> find(18, .. --> find(3, ... I understand how find(11 + 5, .. passes the call to find(11 * 3 .., but I don't understand how find(11 * 3 .. passes the call to find(6 * 3, .. and then to find(1 * 3, .., as the call stack above seems to indicate.

Improve this question
6
  • Might want to read about short circuiting if you're not aware of that. The answer is the || operator determines that null is falsy and attempts the second path starting with the call find(start * 3, "(' + history + ' * 3)") Commented Oct 16, 2019 at 4:53
  • Do findSolution(2) and you'll see the result of the OR having both falsy values. By the way, your quotation marks are wrong. Commented Oct 16, 2019 at 4:58
  • The original actually uses template literals, but I copied this from one of the other SO questions and didn't notice. Editing it. Commented Oct 16, 2019 at 5:01
  • @PatrickRoberts I understand what's happening there. What I'm not understanding is what happens when both expressions on either side of the || are falsy/null. I expect it to then return the call to the original find(1, '1'). Commented Oct 16, 2019 at 5:05
  • "I expect it to then return the call to the original find(1, '1')"... it does, which is null. Bear in mind that the target remains the same. Commented Oct 16, 2019 at 5:09

1 Answer 1

Reset to default
4

I understand how find(11 + 5, .. passes the call to find(11 * 3 .., but I don't understand how find(11 * 3 .. passes the call to find(6 * 3, .. and then to find(1 * 3, ..

First note that there are two types of things that find may return: either a (non-empty) string (history) or null. The first is a truthy value, the second is a falsy value.

You understand that find(16, "(((1 + 5) + 5) + 5)") returns null and so the other part of the ||-expression is evaluated, i.e. find(33, "(((1 + 5) + 5) * 3)").

Just like the left part of || can return null, so also the right part of it can return null. In that case that whole expression returns null to the "parent" call, which also was made from such an || expression.

And so you really get the same thing happening there, but one level higher in the recursion tree. The above was happening when at that higher level find(11, "((1 + 5) + 5)") was executing. It eventually returned null || null, i.e. null, and so then (at that higher level) it goes to the other side of its own || expression and evaluates find(18, "((1 + 5) * 3)"). That also returns null (immediately this time). And so we again have null || null, and backtrack (that's the word!) to yet a higher level in the recursion tree.

The "Parent"

Recursion means that – while the function is executing – a new call of the same function is made. I call the parent the function's execution that made the recursive call and which is waiting for that call to come back with a return value.

That child may also become parent of yet a more nested, grandchild call. So you have a stack of unfinished function executions. When the deepest of those returns a value, the one "above" it will "wake up" and receive that value: it can then continue and make another child call and a similar scenario repeats. If it has no more such calls to make, it will return a value to its parent (backtracking), which was all the time waiting for a recursive call to come back with a value.

Imagine this whole recursive process as a stack. When some code calls this function, the caller's execution context is pushed on a stack, and the execution continues with executing the function. This execution context holds everything the initiating code needs to proceed from the point where it makes the function call. It has variables with their values, the exact place in the code where it made the function call, the parameters it passed to that function call, ...etc.

Then the function may call itself, so again its own execution context is pushed on the stack (the "call stack"), and so the stack may grow. But at some point the function will return a value, and the stack unwinds: the previous execution context is restored, and that parent will continue executing from where it made the recursive call. Execution ends when this call stack is emptied.

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

4 Comments

This is explained well, and I think I'm close to understanding this, but can you edit the answer to elaborate on the "parent" call for me? What is the "parent" call? For example, is it the last truthy expression?
Recursion means that while the function is executing a new call is made. I call the parent the one that made the recursive call and which is waiting for that call to come back with a return value. That child call may also become parent of yet a more nested, grandchild call. So you have a stack of unfinished function executions. When the deepest returns a value the one above it can continue and make another child call.
See addition to answer.
Thank you for the in-depth answer you’ve provided here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.