Recursion and factorial of a number in PHP

Question

<?php  
function factorial_of_a($n)  
{  
    if($n ==0)  
    {  
        return 1;  
    }
    else   
    {    
        return $n * factorial_of_a( $n - 1 );  
    }  
}  
print_r( factorial_of_a(5) );
?>  

My doubt is:

return $n * factorial_of_a( $n - 1 ) ;

In this statement - it gives a result of 20 when $n = 5 and $n - 1 = 4. But how come the answer 120 when I run it? Well, 120 is the right answer... I don't understand how it works. I used for-loop instead and it was working fine.

Answer 1

factorial_of_a(5)

Triggering following calls:

5 * factorial_of_a(5 - 1) ->
5 * 4 * factorial_of_a(4 - 1) ->
5 * 4 * 3 * factorial_of_a(3 - 1) ->
5 * 4 * 3 * 2 * factorial_of_a(2 - 1) ->
5 * 4 * 3 * 2 * 1 * factorial_of_a(1 - 1) ->
5 * 4 * 3 * 2 * 1 * 1

So, the answer is 120.

Consider reading recursive function article on wikipedia.

Also, read this related thread: What is a RECURSIVE Function in PHP?

---

but how come the answer 120 ?

Well, this function will call itself with $n - 1, while $n - 1 is not equals to 0. When it is, then function actually returns result to the program. So it is not returning result instantly, while argument in larger then 0. It is called a "terminate condition" of the recursion.

Answer 2

It will work in this way..

- factorial_of_a(5); 
// now read below dry run code from the bottom for proper understanding
// and then read again from top

   - if n = 0 ; false // since [n = 5]
   - else n*factorial_of_a(n-1); [return 5 * 24] 
   // here it will get 24 from the last line since 4*6 = 24 and pass 
   // it to the value of n i.e. **5** here will make it **120**

     - if n = 0 ; false [n = 4] 
     - else n*factorial_of_a(n-1); [return 4 * 6] 
     // here it will get 6 from the last line since 3*2 = 6 and pass it 
     // to the value of n i.e. **4** here will make it **24**

         - if n = 0 ; false [n = 3] 
         - else n*factorial_of_a(n-1); [return 3 * 2] 
         // here it will get 2 from the last line since 2*1 = 2 and pass it 
         // to the value of n i.e. **3** here will make it **6**

             - if n = 0 ; false [n = 2] 
             - else n*factorial_of_a(n-1); [return 2 * 1] 
             // here it will get 1 from the last line since 1*1 = 1 and pass it 
             // to the value of n i.e. **2** here

                 - if n = 0 ; false [n = 1] 
                 - else n*factorial_of_a(n-1); [return 1 * 1] 
                 // here it will get 1 from the last line and pass it 
                 // to the value of n i.e. **1** here

                     - if n = 0 ; true // since [n = 0] now it will return 1
                     - return 1;

Answer 3

To understand this you need to be clear with the concept of recursion. Recursion means calling a function again and again. Every recursive function has a terminating case and a recursive case. Terminating case tells when will the function stop and recursive case calls the function itself again.

In your code the if condition $n == 0 marks the terminating case, i.e. do not do any calculation if a number is equal to 0 and return 1. The else part is the recursive case [ $n*factorial_of_a($n-1) ]

Now i will explain how it works for $n = 5 :

Since $n is not equal to 0 then else statement is executed which gives 5 *factorial_of_a(4);

Now factorial_of_a(4) is called which gives 4 * factorial_of_a(3);

Now factorial_of_a(3) is called which gives 3 * factorial_of_a(2);

Now factorial_of_a(2) is called which gives 2 * factorial_of_a(1);

Now factorial_of_a(1) is called which gives 1 * factorial_of_a(0);

Now factorial_of_a(0) is called which gives 1

So basically

factorial_of_a(5) = 5 * 4 * 3 * 2 * 1 = 120

Hence the result!

Hope it helped!!

Answer 4

You have to bear in mind that his is a recursion when you call factorial_of_a(5) it will execute this as

factorial_of_a(5)  

// 5 * 24
5 * factorial_of_a(4)

  // 4 * 6
  4 * factorial_of_a(3)

     // 3 * 2
     3 * factorial_of_a(2)

         // 2 * 1
         2 * factorial_of_a(1)

             //will return 1 since it is your base condition
             1 * factorial_of_a(0)