Why does this program keep on running after null i

Question

I'm learning recursion and I understand how the program generally works, but I'm confused why the program continues to work after null is first returned when the value, at 16, is too big.

Basically the code below will run and add 5 to the argument for start each time from 1,6,11 to 16. Since 16 is > 13 it says to return null. How does JavaScript know to go back and try to calculate 13 when it just says return null on line 6?

I'd really appreciate any help. Here's the code from the book I'm looking at:

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

Answer 1

Look at the code - it works in a fiddle:

return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");

This is basically checking the first call against find() and a second call through the || or comparison. When the function returns null. Javascript null is considered false in a logical or operation. So when both find() calls return null, the recursion would stop.

Answer 2

The main culprit is:

  return find(start + 5, "(" + history + " + 5)") ||
         find(start * 3, "(" + history + " * 3)");

Lets assume start is equal to 1 and, like with your code, our target is 13.

1. find() is called with our 1 to begin with. Lets call this Find A.
2. find() gets to the snippet above and is triggered again with a new start value of 1 + 5 (6). Let's call this Find B.
3. Find B also gets to the snippet above and is triggered again with a new start value of 6 + 5 (11). Let's call this Find C.
4. Find C also gets to the snippet above and is triggered again with a new start value of 11 + 5 (16). Let's call this Find D.
5. Find D returns the value null to Find C.
6. Find C executes the OR parameter of the above snippet. find() is triggered again with a new start value of 6 * 3 (18). Let's call this Find E.

See what's happening?

7. Find E, like with our deceased friend Find D returns the value null to Find C.
8. Find C now returns the value null to Find B.
9. Find B executes the OR parameter of the above snippet.

Eventually your recursion will end when a value other than null is returned to your original Find A call, but it still has a way to go before it reaches the original Find A and finally returns a value to our findSolution() function.

For every null response, a new find() call is made. null is a falsey value. Until a truthy value is returned (your history variable in this case), new find() functions will be executed. When the history variable is returned, it gets passed back to the calling function, which passes it back to its calling function, until eventually it makes it back to our Find A function call which passes it back to the findSolution() function.

---

A working visualisation

You'll need to open your JavaScript console for this.

var findIteration = 0;

function findSolution(target) {
  function find(start, history, caller) {
    var thisIteration = ++findIteration;
    console.log("Find Iteration " + thisIteration, "Start: " + start, "Called by: " + caller);
    if (start == target)
      return history;
    else if (start > target)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)", thisIteration) ||
             find(start * 3, "(" + history + " * 3)", thisIteration);
  }
  return find(1, "1", 0);
}

console.log(findSolution(13));

Here's what our console output looks like:

The "Called By" here is the find() method that called it - just like how Find C (iteration 3) calls Find E (iteration 5) in the text example I was giving at the start.

All in all, our find() function was called 9 separate times before finally reaching the correct value.