so, I kinda know how recursion works, to simplify, a function call itself until a condition is met. Now, I am reading eloquentJavaScript, its great. It explain recursion with the following example:
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));
// result: (((1 * 3) + 5) + 5)Now this function with the help of recursion find out how, starting from 1, you can obtain a number only by multiplying by three or adding 5, if possible. If not it returns null, if you match the number it will print the passages (history),thus exiting the recursion.
What I can't understand is how can it guess the sequence of adding and multiplying and do the branching thing. The find function return null if the number more than target, return history if equal, try to add 5 calling itself, or multiplying by 3 also by calling itself. So it shouldn't be able to guess the path to 13, instead it works.
Javascript wise, how is this possible?
Here is how it explains it
To better understand how this function produces the effect we’re looking for, let’s look at all the calls to find that are made when searching for a solution for the number 13.
find(6, "(1 + 5)")
find(11, "((1 + 5) + 5)")
find(16, "(((1 + 5) + 5) + 5)")
too big
find(33, "(((1 + 5) + 5) * 3)")
too big
find(18, "((1 + 5) * 3)")
too big
find(3, "(1 * 3)")
find(8, "((1 * 3) + 5)")
find(13, "(((1 * 3) + 5) + 5)")
found!
How can it goes back? Please help me
What may be missing in your knowledge is how the memory stack is handled during the recursions. Let's do it step by step.
Calling
find(1, "1")
Those variables are in memory stack #0:
current is 1history is "1"target is 13Makes:
find(1 + 5, `(${"1"} + 5)`) || find(1 * 3, `(${"1"} * 3)`);
The first operand will be attempted... So
find(1 + 5, `(${"1"} + 5)`)
Those variables are in memory stack #1:
current is 6history is "(1 + 5)"target is 13Makes:
find(6 + 5, `(${"(1 + 5)"} + 5)`) || find(6 * 3, `(${"(1 + 5)"} * 3)`);
find(6 + 5, `(${"(1 + 5)"} + 5)`)
Those variables are in memory stack #2:
current is 11history is "((1 + 5) + 5)"target is 13Makes:
find(11 + 5, `(${"((1 + 5) + 5)"} + 5)`) || find(11 * 3, `(${"((1 + 5) + 5)"} * 3)`);
find(11 + 5, `(${"((1 + 5) + 5)"} + 5)`)
Those variables are in memory stack #3:
current is 16history is "(((1 + 5) + 5) + 5)"target is 13It now hits the condition
else if (current > target) {
return null;
}
// That is:
else if (16 > 13) {
return null;
}
Memory stack #3 is discarded and memory stack #2 is popped, so the second operand will be evaluated:
current is 11history is "((1 + 5) + 5)"target is 13We now have:
null || find(11 * 3, `(${"((1 + 5) + 5)"} * 3)`);
Get it? We never attempted the second operand yet...
Continue doing it step by step like this and note down the variable values for each recursion step. When it returns, pop a stack and continue until it is all popped.
Also carefully note down who is the caller for each recursion step to know where the returned value goes.