How does this recursion work?

Question

This is an example from Eloquent Javascript:

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of additions and multiplications that produce that number?

I'm having trouble understanding how the recursion is working here, wondering if someone could write out a couple times how find is getting called or some other explanation.

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

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3)

Answer 1

Lets leave the history parameter, we'll get to it later.

The recursion expands to all possible operations. It starts with the value 1 as start.

1. We first check if we reached our destination: goal, if we did- return true, meaning the path we took is correct.

2. Second, we ask- did we go over the bound (goal)? If we did, we should return false since this path can't help us.

3. Otherwise, lets try our two possiblities (We use OR because we need at least one):

   • Call the same function, but set start to start + 5
   • Call the same function, but set start to start * 3

The history variable keeps the steps we take. So if a function call identifies that start == goal it returns it.

Answer 2

goal is your objective and it's set to 24

goal == 24

Now we have this internal function find() that checks to see if start is equal to 24; its not. It also checks to see if start is greater then 24 this is also not true,

find(1 "1")
1 == 24 //false
1 > 24 //false

So it hits the else statement where it calls find again, this is where the null value from the else if() comes in. If the return is null then it calls the || part until it eventually finds the correct answer.

return find(6, "(1 + 5)")
       find(11, "((1 + 5) + 5)")
       find(16, "(((1 + 5) + 5) +5)")
       find(21, "((((1+5) + 5) + 5) +5)")
       //next one returns null!
       //tries * by 3 on 21, 16, and 11 all return null 

so it switches to the ||

return find(3, "(1 * 3)")
       find(8, "((1 * 3) +5)")
       //some calls down +5 path but that returns null
       find(24, "(((1 * 3) + 5) * 3)")

Finally! We have a true return and we have logged the path we took in the history var.

Answer 3

Simply speaking, find(start,goal) will be called recursively as long as the goal value has not been reached. In each call, the current number will be either multuplied by 3 or incremented by 5. The history variable stores the string with the operations performed. The current operation is appended to that string in every iteration.

Explanation:

function findSequence(goal) {

  // This inner function will be called recursively.
  // 'history' is a string with the current operations "stack"
  function find(start, history) {
    if (start == goal)           // if goal is achieved, simply return the result
                                 // ending the recursion
      return history;
    else if (start > goal)       // return null to end the recursion
      return null;
    else
      // One of the 'find' calls can return null - using ||
      // ensures we'll get the right value.
      // Null will be returned if 'start+5' or 'start*3' is
      // greater than our 'goal' (24 in your example).
      // The following line is where a recursion happens.
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }

  // Start with '1'
  return find(1, "1");
}

Answer 4

You just have to create the tree of invocations to figure this out:

findSequence(24)
    find(1, "1")
       find(1 + 5, "(1 + 5)")
           find(6 + 5, "((1 + 5) + 5)")
               find(11 + 5, "(((1 + 5) + 5) + 5)"
                   find(16 + 5, "((((1 + 5) + 5) + 5) + 5)"
                       find(21 + 5, "(((((1 + 5) + 5) + 5) + 5) + 5)"
                          start > goal: return null
                       find(21 * 3, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
                          start > goal: return null
                   find(16 * 3, "((((1 + 5) + 5) + 5) * 3)"
                       start > goal: return null
               find(11 * 3, "(((1 + 5) + 5) * 3)"
                   start > goal: return null
           find(6 * 3, "((1 + 5) * 3)")
               find(18 + 5, "(((1 + 5) * 3) + 5)")
                   find(23 + 5, "((((1 + 5) * 3) + 5) + 5)")
                       start > goal: return null
                   find(23 * 3, "((((1 + 5) * 3) + 5) * 3)")
                       start > goal: return null
               find(18 * 3, "(((1 + 5) * 3) * 3)")
                   start > goal: return null
       find(1 * 3, "(1 * 3)") 
           find(3 + 5, "((1 * 3) + 5)")
               find(8 + 5, "(((1 * 3) + 5) + 5)")
                   find(13 + 5, "((((1 * 3) + 5) + 5) + 5)")
                       find(18 + 5, "(((((1 * 3) + 5) + 5) + 5) + 5)")
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                       find(18 * 3, "(((((1 * 3) + 5) + 5) + 5) * 3)")
                           start > goal: return null
                   find(13 * 3, "((((1 * 3) + 5) + 5) * 3)")
                       start > goal: return null
               find(8 * 3, "(((1 * 3) + 5) * 3)")
                   return "(((1 * 3) + 5) * 3)"
           find(3 * 3, "((1 * 3) * 3)")
               find(9 + 5, "(((1 * 3) * 3) + 5)")
                  find(14 + 5, "((((1 * 3) * 3) + 5) + 5)")
                      find(19 + 5, "(((((1 * 3) * 3) + 5) +5) + 5)")
                         return "(((((1 * 3) * 3) + 5) +5) + 5)"
                      find(19 * 3, "((((1 * 3) * 3) + 5) *3)")
                          start > goal: return null
               find(9 * 3, "(((1 * 3) * 3) * 3)")
                    start > goal: return null

Answer 5

Think of the infinite combinations of adding 5 and multiplying by 3 like a binary tree. At the top is the easiest number to calculate, 1 (in effect a "no steps necessary" answer). Down one level and to the left is 1+5, and to the right is 1*3. At each level the equation resolves to a new value (with a more complex history). This equation is navigating through that tree until it finds a node that equates to the goal. If a node on a branch of the tree produces a value greater than your goal, then it returns null (thus halting the further recusing down that branch, this is because both operations only increase the value so once you end up greater than there is no point to keep looking), if the value of a node equates to the goal then it is returned as the answer (along with the path it used to get there). When the value is less than then both paths could potentially hold the answer so it calls find on each. Here is where JavaScript's "truthy" Boolean logic comes in. By using the || (OR) operator JavaScript will first look down the +5 side of the tree. if 0 or null are returned then the other call (to look down the *3) will execute. If any return evaluates to a non false value then it will get returned up the stack and the search will end.