Math: Factorials and PHP

18 06 2010

What is up with the technical questions based on an understanding of math? When was the last time I actually worked for a client who needed me to find factorials using PHP? Oh, well, instead of procrastinating by dwelling on past glories, let’s consider the following technical question:

Write a recursive function that calculates a factorial of an integer.
Note: the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n

Yeah, well that definition is as crystal clear as uh mud to those who are mathematically disinclined. So, to translate into plain English, factorials involve using positive, whole numbers. You get a factorial by multiplying a number successively by one less than itself until you reach 1. For example the factorial of 3 represented mathematically as 3! is as follows:

3 * 2 * 1

So, the factorial of 3 (shorthand: 3!) equals 6. Easy?

// coding problem:

// write a function definition for factorial() here.

$num = 5;

echo factorial($num);

// Output: 120

You could approach this problem by doing the knee-jerk thing of using recursion since it’s so easy to do mathematically. So, why not do it in code, makes sense? Or does it?

<?php
function factorial($num) {
if ($num == 0) return 1;
return $num * factorial($num - 1);
}
echo factorial(5);
// output: 120

You will note, however, that recursion is one of those old-fashioned techniques that is not highly encouraged or used predominantly on the web. Why is that? Performance. Yeah, it can make your web server crawl. See my previous post about fibonacci numbers. But, what other way is there if you want to get a factorial? How about iteration? See code below:

function factorial($num)
{
for ($result = 1, $num = 5, $endpoint=1; $num >= $endpoint; $num--) {
$result *= $num;
}
return $result;
}
echo factorial(5);

With iteration you can easily get the factorial of a number and avoid the trade-off of slow web server performance that can be an issue when one employs recursion.

This work is licensed under a Creative Commons License
.

Advertisements

Actions

Information

One response

24 11 2014
Sancol Gates

great,This is the entrance test question when I had interview..

Thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: