Menu
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)
647
Recursive Functions in PythonA recursive function is a function defined in terms of itself via self-referential expressions. This means that the function will continue to call itself and repeat its behavior until some condition is met to return a result.
When function is called within the same function, it is known as recursion in C++. The function which calls the same function, is known as recursive function. A function that calls itself, and doesn't perform any task after function call, is known as tail recursion.
When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for the called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call.
A recursive function calls itself, so the memory for a called function is allocated on top of the memory allocated for calling the function. Remember, a different copy of local variables is created for each function call.
The function runs a rather simple brute force search with backtracking: at each invocation level it tries adding 5 to the number, and see if starting from the resultant number gets you to the goal. If it does, the result is returned; otherwise, the number is multiplied by 3, and the search for the goal continues from that new number. As the recursion goes along, the textual representation of the expression producing the number is passed to the next invocation levels.
The search for 14 goes as follows:
(1, "1")
(5, "1+5")
(10, "(1+5)+5")
(15, "((1+5)+5)+5") <<= Fail
(30, "((1+5)+5)*3") <<= Fail
(15, "(1+5)*3") <<= Fail
(3, "1*3")
(8, "(1*3)+5")
(13, "((1*3)+5)+5")
(18, "(((1*3)+5)+5)+5") <<= Fail
(39, "(((1*3)+5)+5)*3") <<= Fail
(24, "((1*3)+5)*3") <<= Fail
(9, "(1*3)*3")
(14, "((1*3)*3)+5) <<= Success!
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
The best way for you to learn this would be to trace through the code in the JavaScript debugger.
Have you used the debugger before? It's really fun and enlightening and easy too.
Simply add a debugger; statement where you want the code to stop. A good place would be just before you call findSequence():
debugger;
console.log(findSequence(24));
Now load your page in Chrome with the Developer Tools open. Your code will stop on that debugger; line. Find the button that lets you Step Into your code (over on the right above the Watch Expressions panel). Click that button to step into the findSequence() call. Each time you click it, it will step into the next line of code, which includes going into each recursive call.
Whenever the code is stopped, you can hover the mouse over any variable to view it, or look at the variables in the panel on the right. There is also a Call Stack that will show you exactly where you are in the recursive calls.
I'm sure somebody could explain the recursion to you, but you will learn a lot more if you actually experience it by stepping through your code in the debugger.
26
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
