How Is This Recursive Function Changing The 'history' Variable?

I feel so close to figuring this out, but I can't quite understand this function.. I get how the function keeps checking for the target number and if it gets too high, it returns

Solution 1:

You are doing what's called a depth-first search via recursion. Everyone groks recursion a little differently. Something will eventually make it click for you.

I'd like to make a couple of annotations in your code that help it print out a more natural transcript of what transpires. Hopefully that will help some.

But I think the most important thing is to visualize how many levels deep in the recursion you are with some indenting. When you log during a recursive depth-first search, you are basically making a binary tree where the output is like:

Root
   Root > Left
   Root > Right

And it starts to nest with recursion like this:

Root
   Root > Left
      Root > Left > Left
      Root > Left > Right
   Root > Right
      Root > Right > Left
      Root > Right > Right

And instead of "Left" and "Right" paths, you are creating "+5" and "*3" branches of exploration. In your recursion you explore the +5 branch of the tree first looking for a solution. If you don't find it, then you explore the *3 branch of the tree. When nothing is found, it just means that the answer does not lie on the branch you are considering and a different choice earlier in the tree must be made.

Some back-tracking appears to occur when both avenues are tried and neither succeeds. But really it's just a conclusion of a hypothesis made where we say "can we get there if we +5?" or "can we get there if we *3?" If the answer is no to both, then you just can't get there from where you are. You don't have to actually back-track, the beauty of recursion is that you got where you are in the search because someone invoked you as part of a "what if...". If your entire search comes up empty, no problem. You just abandon your current branch of the search and the "someone" that invoked you will try something else on a different branch.

The state of your recursion (which branch you are exploring) is kept on your call stack. That's where we actually "back up".

history is never modified. We just explore different versions of history that are constructed via recursion. Each history is its own copy and it only ever gets longer (a left or right branch in the search tree) or gets abandoned and the search continues from some other history elsewhere in the recursion.

So here's your code with some indenting and some wordy descriptions of what's going on at each step that hopefully ties back to the recursion a little more closely.

functionspaces(indent) {
  return'    '.repeat(indent);
}

functionfindSolution(target) {
  functionnope(indent, history) {
    console.log(spaces(indent) + `Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to ${target}, but not by starting from ${history}.`);
    returnfalse;
  }
  functionbadnews(history) {
    console.log(`I've tried everything and there's just no way of getting to ${target}.  :(`);
    returnfalse;
  }
  functionfind(current, which, history, indent) {
    if (current == target) {
      console.log(spaces(indent) + `${which}, and guess what...we finally found a solution! Because ${history} = ${current}.  So we can stop now. :)`);
      return history;
    } elseif (current > target) {
      //console.log(`CURRENT AT NULL: ` + current);console.log(spaces(indent) + `${which}, we reached a dead end because ${history} = ${current} which is unfortunately already bigger than ${target}.`);
      returnnull;

    } else {
      console.log(spaces(indent) + `${which}, ${history} looks promising because it equals ${current}, which is still less than ${target}.  We'll try two ways of getting to ${target} from here.`);
      returnfind(current + 5, 'First, by adding 5', `(${history} + 5)`, indent+1) ||
        find(current * 3, 'Second, by multiplying by 3', `(${history} * 3)`, indent+1) ||
        nope(indent+1, history);
    }
  }
  returnfind(1, 'Initially', "1", 0) || badnews();
}
console.log(`${findSolution(24)}`);

Output is copied below, just in case. Sorry, there's no wrapping of the output because indenting is more important so you can see how many levels deep in the recursion you are, and what causes a back-track. You can run the snippet if you find the snippet console output more readable.

Initially, 1 looks promising because it equals 1, which is still less than 24.  We'll try two ways of getting to 24 from here.
    First, by adding 5, (1 + 5) looks promising because it equals 6, which is still less than 24.  We'll try two ways of getting to 24 from here.
        First, by adding 5, ((1 + 5) + 5) looks promising because it equals 11, which is still less than 24.  We'll try two ways of getting to 24 from here.
            First, by adding 5, (((1 + 5) + 5) + 5) looks promising because it equals 16, which is still less than 24.  We'll try two ways of getting to 24 from here.
                First, by adding 5, ((((1 + 5) + 5) + 5) + 5) looks promising because it equals 21, which is still less than 24.  We'll try two ways of getting to 24 from here.
                    First, by adding 5, we reached a dead end because (((((1 + 5) + 5) + 5) + 5) + 5) = 26 which is unfortunately already bigger than 24.
                    Second, by multiplying by 3, we reached a dead end because (((((1 + 5) + 5) + 5) + 5) * 3) = 63 which is unfortunately already bigger than 24.
                    Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((((1 + 5) + 5) + 5) + 5).
                Second, by multiplying by 3, we reached a dead end because ((((1 + 5) + 5) + 5) * 3) = 48 which is unfortunately already bigger than 24.
                Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((1 + 5) + 5) + 5).
            Second, by multiplying by 3, we reached a dead end because (((1 + 5) + 5) * 3) = 33 which is unfortunately already bigger than 24.
            Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((1 + 5) + 5).
        Second, by multiplying by 3, ((1 + 5) * 3) looks promising because it equals 18, which is still less than 24.  We'll try two ways of getting to 24 from here.
            First, by adding 5, (((1 + 5) * 3) + 5) looks promising because it equals 23, which is still less than 24.  We'll try two ways of getting to 24 from here.
                First, by adding 5, we reached a dead end because ((((1 + 5) * 3) + 5) + 5) = 28 which is unfortunately already bigger than 24.
                Second, by multiplying by 3, we reached a dead end because ((((1 + 5) * 3) + 5) * 3) = 69 which is unfortunately already bigger than 24.
                Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((1 + 5) * 3) + 5).
            Second, by multiplying by 3, we reached a dead end because (((1 + 5) * 3) * 3) = 54 which is unfortunately already bigger than 24.
            Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((1 + 5) * 3).
        Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (1 + 5).
    Second, by multiplying by 3, (1 * 3) looks promising because it equals 3, which is still less than 24.  We'll try two ways of getting to 24 from here.
        First, by adding 5, ((1 * 3) + 5) looks promising because it equals 8, which is still less than 24.  We'll try two ways of getting to 24 from here.
            First, by adding 5, (((1 * 3) + 5) + 5) looks promising because it equals 13, which is still less than 24.  We'll try two ways of getting to 24 from here.
                First, by adding 5, ((((1 * 3) + 5) + 5) + 5) looks promising because it equals 18, which is still less than 24.  We'll try two ways of getting to 24 from here.
                    First, by adding 5, (((((1 * 3) + 5) + 5) + 5) + 5) looks promising because it equals 23, which is still less than 24.  We'll try two ways of getting to 24 from here.
                        First, by adding 5, we reached a dead end because ((((((1 * 3) + 5) + 5) + 5) + 5) + 5) = 28 which is unfortunately already bigger than 24.
                        Second, by multiplying by 3, we reached a dead end because ((((((1 * 3) + 5) + 5) + 5) + 5) * 3) = 69 which is unfortunately already bigger than 24.
                        Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((((1 * 3) + 5) + 5) + 5) + 5).
                    Second, by multiplying by 3, we reached a dead end because (((((1 * 3) + 5) + 5) + 5) * 3) = 54 which is unfortunately already bigger than 24.
                    Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from ((((1 * 3) + 5) + 5) + 5).
                Second, by multiplying by 3, we reached a dead end because ((((1 * 3) + 5) + 5) * 3) = 39 which is unfortunately already bigger than 24.
                Sadly we've exhausted all possible ways of getting there from this starting point.  We may still be able to get to 24, but not by starting from (((1 * 3) + 5) + 5).
            Second, by multiplying by 3, and guess what...we finally found a solution! Because (((1 * 3) + 5) * 3) = 24.  So we can stop now. :)
(((1 * 3) + 5) * 3)

Solution 2:

Whenever your current > target so it returns null and you're find(current * 3,(${history} * 3)) will be evaluated

suppose

((((1 + 5) + 5) + 5) + 5)   ---> This is the current value of history

So the current value at present is 21

Now when you reach

find(current + 5, `(${history} + 5)`) ||
        find(current * 3, `(${history} * 3)`);

It calls the find(21 + 5, (${history} + 5))) since the value of current > target so the value returned from this call will be null, since null is falsy value so the second operand will be call,

  find(21 * 3, `(${history} * 3)`);   <--- so thisis the final value returned form this invocation

So the value of history here will

(((((1 + 5) + 5) + 5) + 5) * 3)

---

functionfindSolution(target) {
  functionfind(current, history) {
    if (current == target) {
      return history;
    } elseif (current > target) {
      console.log(current, ' ---> ', `HISTORY AT NULL:  ${history}`);
      returnnull;

    } else {
      console.log(current,' ---> ', `${history}`);
      returnfind(current + 5, `(${history} + 5)`) ||
        find(current * 3, `(${history} * 3)`);
    }
  }
  returnfind(1, "1");
}
console.log(findSolution(8));