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.