I'm trying to understand this recursion code and have become stuck

Question

I think I'm getting a grasp on recursion in Javascript but would appreciate some clarity on a specific recursion code I'm reviewing in a book I'm reading

The code below as I understand is proceeding through a few steps, which I'll explain if you can correct any errors in my understanding I would really appreciate it:

• The findSolution function is looking for a solution where you either add 5 or multiply by 3 to get to 24

• The function find is where the recursion happens to find this solution, the statement if (start == target)is what tells the recursion to end when it finds the solution and return the history of how this happens

• The return statement in lines 8-9 starts with (1 + 5) which equals 6, so it then starts back at the top proceeding through the if statements which isn't met then proceeds to the return statement again this time with (6 + 5) which equals 11

• It proceeds through this until one of the if statements is met. When start is higher than the target the function then proceeds to the the other side of the || statement and starts with (1 * 3) with the history being equivalent to "(1 * 3)"

What I'm unsure of is why does the function proceed through first part adding 5 to the (1 * 3) on the next iteration, how does the function know to add 5 and then on the next iteration multiply by 3? Why does it not continue to add 5 and then do so until it is too big and return null?

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(24));
// → (((1 * 3) + 5) * 3)

Answer 1

First, the function find starts with 1. Inside find:

• if what we have is equal to the result we return the history that got us here
• if not, we see if we have passed the target (what we have is already greater than the target so multiplying by 3s or adding 5s won't get us to it).
• lastly, if we are bellow the target. Then we take what we have so far (the history, both literal (the string) an numerical (the result)) start two branches one by adding a 5 and the other by multiplying by 3.

The first call to find was with the result of 1 and the history of "1".

Inside that first find the test (start == target) will fail since (1 != 24), the second test (start > target) will fail too because (1 <= 24). So we executes what inside the else. So we call find which will take a result of (1 + 5) and a history of ("( 1 + 5)") and we check if we've got a history that got us to 24 (the returned value won't be null) or if the returned value is null then call another find with the result of (1 * 3)) and the history of ("( 1 * 3 ") and we check if we got a returned value different from null (the right answer) or not (there is no answer).

It will be best if it was represented by a tree view with all the possible calls:

[1] -> [1 + 5] -> [6 + 5] -> [11 + 5] -> [16 + 5] -> [21 + 5] >> branch terminated (26 > 24)
   |          |          |           |            -> [21 * 3] >> branch terminated (63 > 24)
   |          |          |            -> [16 * 3] >> branch terminated (48 > 24)
   |          |           -> [11 * 3] >> branch terminated (33 > 24)
   |           -> [6 * 3] >> returns the right result (24 == 24)
   |
   |
   | We will never have the next branch because we already got a result.
    -> [1 * 3] -> [3 + 5] -> [8 + 5] -> [13 + 5] -> [18 + 5] -> [23 + 5] >> branch would have been terminated (28 > 24)
              |          |          |           |            -> [23 * 3] >> branch would have been terminated (69 > 24)
              |          |          |            -> [18 * 3] >> branch would have been terminated (54 > 24)
              |          |           -> [13 * 3] >> branch would have been terminated (39 > 24)
              |           -> [8 * 3] >> would have been a correct answer if we haven't already got one
               -> [3 * 3] -> [9 + 5] -> [14 + 5] -> [19 + 5] >> would have been a correct answer if we haven't already got one
                         |          |            -> [19 * 3] >> terminated ...
                         |           -> [14 * 3] >> terminated ...
                          -> [9 * 3] >> terminated ...

The terminated branches means that the condition (start > target) was met so a returned null to the caller which will have 3 possible outcomes:

1. If the caller is another find and the find that returned null is the first find in find(start + 5, "(" + history + " + 5)") || find(start * 3, "(" + history + " * 3)") then we call find with a * 3 branch.
2. If the caller is another find and the find that returned null is the second find in find(start + 5, "(" + history + " + 5)") || find(start * 3, "(" + history + " * 3)") then we return a null which will terminates the parent barnch (this find).
3. If the caller is findSolution then the target was never acheived using just + 5 and * 3 combo.

The find that returned a correct answer (in other words the find that met the condition start == target) will prevent more branches to be created (it will return a non null result which will be returned by its caller and its caller before it ... all the way to findSolution) so if we are at the first find in find(start + 5, "(" + history + " + 5)") || find(start * 3, "(" + history + " * 3)") the second one will never be executed.

Answer 2

Here is a version of your code that will print an execution tree for you so that you can follow along with all the different permutations that the algorithm is, in fact, trying:

function findSolution(target) {
  function find(start, history, trace) {
    trace.push(history)
    if (start == target) {
      console.log(trace.join(' => ') + ' => ' + start + ' == ' + target);
      return history;
    }
    if (start > target) {
      console.log(trace.join(' => ') + ' => ' + start + ' > ' + target);
      return null;
    }
    return find(start + 5, "(" + history + " + 5)", [].slice.call(trace)) ||
           find(start * 3, "(" + history + " * 3)", [].slice.call(trace));
  }
  return find(1, "1", []);
}
findSolution(24)

Here is the execution tree:

1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) + 5) => ((((1 + 5) + 5) + 5) + 5) => (((((1 + 5) + 5) + 5) + 5) + 5) => 26 > 24
1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) + 5) => ((((1 + 5) + 5) + 5) + 5) => (((((1 + 5) + 5) + 5) + 5) * 3) => 63 > 24
1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) + 5) => ((((1 + 5) + 5) + 5) * 3) => 48 > 24
1 => (1 + 5) => ((1 + 5) + 5) => (((1 + 5) + 5) * 3) => 33 > 24
1 => (1 + 5) => ((1 + 5) * 3) => (((1 + 5) * 3) + 5) => ((((1 + 5) * 3) + 5) + 5) => 28 > 24
1 => (1 + 5) => ((1 + 5) * 3) => (((1 + 5) * 3) + 5) => ((((1 + 5) * 3) + 5) * 3) => 69 > 24
1 => (1 + 5) => ((1 + 5) * 3) => (((1 + 5) * 3) * 3) => 54 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) + 5) => (((((1 * 3) + 5) + 5) + 5) + 5) => ((((((1 * 3) + 5) + 5) + 5) + 5) + 5) => 28 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) + 5) => (((((1 * 3) + 5) + 5) + 5) + 5) => ((((((1 * 3) + 5) + 5) + 5) + 5) * 3) => 69 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) + 5) => (((((1 * 3) + 5) + 5) + 5) * 3) => 54 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) + 5) => ((((1 * 3) + 5) + 5) * 3) => 39 > 24
1 => (1 * 3) => ((1 * 3) + 5) => (((1 * 3) + 5) * 3) => 24 == 24

Answer 3

maybe this makes it more clear what happens.

I've just added a depth-argument to the find-function to determine the recursive-depth, and a console.log() to log all recursive calls.

function findSolution(target) {
    //added a depth-property to show the recursion better
    function find(start, history, depth) {
        //simply log all calls in order
        console.log("%s%d == %s", "|  ".repeat(depth), start, history);

        if (start == target)
            return history;
        else if (start > target)
            return null;
        else
            return find(start + 5, "(" + history + " + 5)", depth+1) ||
                   find(start * 3, "(" + history + " * 3)", depth+1);
    }
    return find(1, "1", 0);
}

console.log(findSolution(24));

Answer 4

It actually did go through every possible cases that you mentioned. It did continue to add 5 until it was too big and return null (in this case find(start + 5, "(" + history + " + 5)") === null (false) so the result will come from the other branch.

It's really hard to explain cause you need to understand execution stack or maybe draw a tree of execution. Let me know how can I help