The answer to last week’s Problem of the Week is that the following definitions represent the factorial of the given non-negative integer:

Mathematical Definition

Function Definition Condition
unnamed(n) = 1 if n = 0
n × unnamed(n – 1) if n > 0

JavaScript Definition

function unnamed(n) {
if(n == 0)
return 1;
if(n > 0)
return n * unnamed(n - 1);
}

Although it may have been easy for some people to follow, for those of you who are not familiar with recursion, it may have been a bit difficult. Let’s use the number 4 as an example to step through the process:

1. When we pass 4 into unnamed we get the following definition for the output:
unnamed(4) = 4  × unnamed(4 - 1) = 4 × unnamed(3)
2. Now we have to find the definition for passing 3 into unnamed:
unnamed(3) = 3  × unnamed(3 - 1) = 3 × unnamed(2)
3. Now we have to find the definition for passing 2 into unnamed:
unnamed(2) = 2  × unnamed(2 - 1) = 2 × unnamed(1)
4. Now we have to find the definition for passing 1 into unnamed:
unnamed(1) = 1  × unnamed(1 - 1) = 1 × unnamed(0)
5. Now we have to find the definition for passing 0 into unnamed:
unnamed(0) = 1
6. Now we go back to step 4 and replace unnamed(0) with 1:
unnamed(1) = 1  × 1 = 1
7. Now we go back to step 3 and replace unnamed(1) with 1:
unnamed(2) = 2  × 1 = 2
8. Now we go back to step 2 and replace unnamed(2) with 2:
unnamed(3) = 3  × 2 = 6
9. Now we go back to step 1 and replace unnamed(3) with 6:
unnamed(4) = 4  × 6 = 24

After stepping through each part of the process, you can more easily see the pattern.

• unnamed(4) is really equal to 4 × 3 × 2 × 1 × 1
• unnamed(3) is really equal to 3 × 2 × 1 × 1
• unnamed(2) is really equal to 2 × 1 × 1
• unnamed(1) is really equal to 1 × 1
• unnamed(0) is really equal to 1
NOTE: The above (0! = 1) is more of a technicality that many people don’t really think about for factorial.

1 Comment

POW – Unnamed Function #1 | Chris West's Blog · February 13, 2012 at 9:30 AM

[…] to this Problem of the Week was posted on February 13, 2012 at 12:00 AM (EST) and can be found here. This entry was posted in Blog, JavaScript, JScript, Math, Problem of the Week and tagged Math, […]