Factorial is expressed as some number ( n) followed by an exclamation point, like so:
n! or 5!
The function is defined as the product of the number n (must be an integer) multiplied by all positive integers less than that number, so 5! =5*4*3*2*1.
n! =n*(n-1)*(n-2)*...*1
This formula is helpful, but it's not recursive. If we compress the last part of the formula though, or take out the 5* part, we notice the remainder is 4*3*2*1 which is the same as 4!. So 5! = 5 * 4!.
Again we do the same and see 4! = 4*3!. And so on. One interesting note is that 0! =1. 0! = 1 will become an exit condition in our formula later.
So we define two cases for our function.
if n = 1 or n = 0, then the function will return 1. if n > 1 then return n * (n-1)!
In PHP this looks like:
<?php function factorial( $n ) { if ($n == 0 || $n== 1) { // $n == 0 or $n == 1 is the exit condition return 1; } else { // the next line contains our recursive call return ( $n * factorial ($n-1)); } } ?>
Next thing to do is make sure it passes the rules above. The function has to have an exit condition. It does. We know the function value explicitly whenever $n is 0 or 1 and the function returns 1 whenever this condition is met, so we have an exit condition. Secondly, it must make different function calls. We know the initial call was factorial( $n ) and the call it makes in the function is to factorial( $n-1), so it passes this test. Lastly, we have to believe it works. I do. If you were to trace this function for factorial (5) you would see something like:
