Russian Nesting Dolls
This post is primarily for those readers who are working through the Codecademy.com course on javascript. I was having trouble with mastering the recursion problem for solving factorials there and noticed that many others were in the same boat.
This code was really blowing my mind. I was having the worst time understanding it. I was OK with the idea of recursion, but I don’t think I was really understanding it.
I was following the code and could see it is working, but didn’t see why it actually returned the correct value. Additionally, I had a conceptual block – i.e. how does the code store the value of each recursion without a variable?
Here’s the problem:
Write a recursing code that solves for the factorial of any given value.
Recall that factorials are the product of all numbers from 1 to n, where n is the value you are solving for. For example, the factorial of 3 : In mathematical terms this is written, 3!, so
3! = 1*2*3 = 6
4! = 1*2*3*4 = 12
The problem suggests that you set a ‘base case’ as returning 1 if n === 0, and that you use a terminator to prevent crash if negative numbers are entered (because they will otherwise never get to the terminator)
Here’s my code:
function factorial(n) {
if (n<0){
console.log(“We can only compute factorials from positive integers”);
return; // the catch-all in case a negative number is entered
}
if (n ==0){
return 1; // the base case
}
else{
return n* factorial (n-1); // the nested function call
}
}
factorial(4); // function call to test program
If we start at 4 (as an example), then we go through the code and get to the nested function call that says
return n * factorial(n-1)
if we sub in the actual values for n, it would read:
return (4) * factorial(3)
But factorial(3) is not a number – it is a function call, so before (4) is multiplied by anything, it sends a new value to factorial. This keeps happening until we get to n=0. At that point we’re at the base case and no further recursion will happen – the code simply returns 1.
So, we have to start moving our way back out of the loop. We set n=1 here, so the innermost recursion actually looks like this:
return 1* factorial(0)
because factorial(0) returns 1, we are actually doing this:
return 1*1 (* = 1 *)
then we back out to the next step:
return 2* 1 (* = 2 *)
then we get to…
return 3*2… (* = 6 *)
return 4*6 (* = 24 *)
Or, if you can see this more clearly, this is how the computer sees the code:
return 4 * (return 3 * (return 2 * (return 1 * (1))));
work backwards doing the math from the inside out:
1*1 = 1
2*1 = 2
3*2 = 6
4*6 = 24
Q.E.D.
postscript: I just received a reply to my post on codecademy.com from a moderator, Alex. He directed me towards an article he had written explaining the same topic using a very elegant flow diagram. You can find that article here. – I had to write this as a postscript, because his article is so clear that if you read it first, you would have no need to read mine.
The Quincunx – A triangular pegboard that will create a nice normal distribution as balls are dropped from the top and bounce down randomly over the triangular array of pegs.
DownHouseSoftware 