Question about the recursion

Hello, Campers!

I hope someone will help me to understand this.

Reading the book Eloquent Javascript I came across the RECURSION topic: https://eloquentjavascript.net/03_functions.html#p_mWzvA1dWtJ

There is a code snippet:

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

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

If we call the console.log(findSolution(24)); the output will be (((1 * 3) + 5) * 3).

My question is: why do it starts from 1 if we have not declared the current to be equal to 1 from the very beginning.

Thanks for any explanation!

Here you are defining current to be 1


Here you define the function find()

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

The function takes two arguments (current, history)


Your function findSolution() return find() while passing it 1 and '1' for current and history

Thanks.

But it is still not clear for me. Maybe, I just do not understand the flow of the function.

Here is they I understand it works:

  1. I call the findSolution() function with argument 24 via:
console.log(findSolution(24));
  1. it enters the function findSolution() and see:
function findSolution(target) {
  function find(current, history) { ... }
  return find(1, "1");
}
  1. then it enters the find() function and see:
    if (current == target) {
      return history;
    } else if (current > target) {
      return null;
    } else {
      return find(current + 5, `(${history} + 5)`) ||
             find(current * 3, `(${history} * 3)`);
    }
  1. after it compares the current and the target and on this point as far as I understand the current value is not defined yet.

So how is that possible the current is equal to 1 at this point?

Thank you.

Here is what is happening
The function findSolution() is triggered with target quals 24
and it should return find(1, "1")

Now the function find()
if (current == target) // current is 1 and target is 24 so this is not true
else if (current > target) // current which is 1 is not larger that target

So, we find ourselves here

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

Well-well. Seems like I’ve understood now.

1. function findSolution(target) {
2.   function find(current, history) { ... }
3.   return find(1, "1");
4. }

On line 2 we declare the function find() and only on line 3 we invoke it with the following options:
current = 1 and history = "1". And once the find(1, "1") is invoked the recursion begins.

Thank you @Tchoukoualeu!

2 Likes

I think you should keep on looking for a good explanation. I’ve just gone through the code again and I think my explanation is not complete at all.

try looking at what happens using JavaScript Tutor

after that if you still have doubts I will try to write the long explanation

1 Like

WOW! What a great resource!

Thank you very much. I need time to check it and understand how it works.

If I need help, I will be back and answer :slight_smile:

Hi again,

I’ve checked that tool and it appeared to be a very useful!

However, I could not understand how the function returns to the previous state when it return null.

Here is the code I’m running in that JS TUTOR:

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

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

There are 42 steps at all. On step 15 the find() returns the null value. How is that possible that on step 16 it forgets the history which was equal to "(((1 + 5) + 5) + 5)" on the step 15 and is equal to "((1 + 5) + 5)" on step 16.

I would really appreciate your explanation!

when you have ||, if the first one is a falsy value (in this case if the first function return null, the other is executed)
here visualization of what each function returns, it is first tried to add 5, and if that doesn’t bring to anything, then to multiply by 3, note that once a null is returned a new branch is temted, so the history changes again, but it is not forgotten, just discarded because that history brings to a null value

findSolution(13)
  |
find(1, ("1")) --- find(6, "(1 + 5)") --- find(11, "((1 + 5) + 5)") --- find(16, "(((1 + 5) + 5) + 5)") --- null
  |                  |                      |
  |                  |                    find(33, "(((1 + 5) + 5) * 3)") --- null
  |                find(18, "((1 + 5) * 3)") --- null
find(3, "(1 * 3)") --- find(8, "((1 * 3) + 5)") --- find(13, "(((1 * 3) + 5) + 5)") --- "(((1 * 3) + 5) + 5)"
3 Likes

Nice! Thank you all very much!

At least, I understood how this code snippet works)

I guess, I need a bit more practice with recursive functions in order to completely understand them and how to use them.

in most cases with recursion you have a a straight line, but the principle is the same, keep going till the returned value is not a function, and then each function will return that value till it reaches the outside