PHP Program to Find Factorial Using Recursion

You can find the factorial of a number in PHP using recursion by defining a function like function factorial($n) { return $n <= 1 ? 1 : $n * factorial($n - 1); } and calling it with the desired number.

Examples

Input0

Output1

Input5

Output120

Input1

Output1

How to Think About It

To find the factorial using recursion, think of the problem as multiplying the number by the factorial of the number just before it. Keep doing this until you reach 1, where the factorial is 1 by definition. Use a function that calls itself with a smaller number each time until it hits this base case.

Algorithm

1

Get the input number n

2

Check if n is less than or equal to 1

3

If yes, return 1 as factorial of 0 or 1 is 1

4

Otherwise, return n multiplied by factorial of n minus 1

5

Repeat the process until base case is reached

Code

php

<?php
function factorial($n) {
    if ($n <= 1) {
        return 1;
    } else {
        return $n * factorial($n - 1);
    }
}

echo factorial(5); // Output: 120

Output

120

Dry Run

Let's trace factorial(5) through the code

1

Call factorial(5)

5 > 1, so return 5 * factorial(4)

2

Call factorial(4)

4 > 1, so return 4 * factorial(3)

3

Call factorial(3)

3 > 1, so return 3 * factorial(2)

4

Call factorial(2)

2 > 1, so return 2 * factorial(1)

5

Call factorial(1)

1 <= 1, so return 1

6

Return values multiply back

2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24, 5 * 24 = 120

Call	Return Value
factorial(1)	1
factorial(2)	2
factorial(3)	6
factorial(4)	24
factorial(5)	120

Why This Works

Step 1: Base Case

The function stops calling itself when the input is 1 or less, returning 1 because factorial of 0 or 1 is 1.

Step 2: Recursive Call

For numbers greater than 1, the function calls itself with the number minus one, building the factorial step by step.

Step 3: Multiplying Results

Each recursive call returns a value that is multiplied by the current number, combining to form the factorial.

Alternative Approaches

Iterative approach

php

<?php
function factorial_iterative($n) {
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}

echo factorial_iterative(5); // Output: 120

This uses a loop instead of recursion, which can be faster and avoids stack overflow for large numbers.

Using PHP built-in function (gmp_fact)

php

<?php
// Requires GMP extension
echo gmp_fact(5); // Output: 120

This uses a built-in function for factorial, which is optimized but requires the GMP extension.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself n times, so the time grows linearly with the input number.

Space Complexity

Each recursive call adds a layer to the call stack, so space used is proportional to n.

Which Approach is Fastest?

The iterative approach uses constant space and is generally faster, while recursion is simpler to write but uses more memory.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Simple code, small inputs
Iterative	O(n)	O(1)	Large inputs, performance
Built-in (gmp_fact)	Optimized	Optimized	Best performance if GMP available