Recursion in PHP - Factorials

(Page 2 of 4 )

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:

factorial (5) Ã’ return 5 * factorial (4) -> return 4 * factorial (3) -> return 3 * factorial (2) -> return 2 * factorial (1) -> return 1

The function would finally return 120 as the result of factorial (5).

Next: Fibonacci >>
 

More Miscellaneous Articles
More By Codewalkers

Comments On: Recursion in PHP

· I know its nit-picking, but the example code above is a perfect example of recursive...    · Oh. Comments by tutorial rather than by page. The code I am referring to in the...    · You are correct. It also doesn't check to see that you are passing in a integer or...    · The code for factorials is not significantly simpler than safe code, just lazier. ...    · There is an error in listing of last Procedure. In line: " for ($i = 1; $i <...    · <?phpfunction f($c) { if ($c<2) throw new Exception('Input out of range'); $f...   >>> Post your comment now!