DEV Community

loading...
Cover image for How Recursion works behind the scene in PHP

How Recursion works behind the scene in PHP

Keramot UL Islam
WordPress Enthusiast. Loves PHP, and JavaScript.
Originally published at blog.abmsourav.com ・2 min read

Recursion is a programming technique where a function calls itself. Recursion is also a technique of “Making a loop in a functional way”.
Recursive functions have two parts. “Base case” and “The Recursive function”.

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

Wikipedia

Skeleton of a Recursive function:

function skeleton() {
    // Base case

    // Recursive function
}

Before we move forward, we need to know about Factorial.
It’s a mathematical term. The factorial of a positive integer n, denoted by n! and is the product of all positive integers less than or equal to n.
n! = n * (n – 1) * (n – 2) * (n – 3) * ... .. * 3 * 2 * 1

Example: 5! = 5 * 4 * 3 * 2 * 1 = 120
Here,
5! = n!, n = 5, (n – 1) = 4, (n – 2) = 3, ... ..

Here are a couple of things about factorial —

  1. Can’t be a negative number
  2. Factorial of 0 is equal to 1

Full article with Diagram Click Here

Now let’s create a Recursive Function of Factorial —

function fact($n) {
    // Base case
    if ( $n === 0 ) {
        return 1;
    }

    // recursive function
    return $n * fact( $n - 1 );
}

echo fact(4); // 4 * 3 * 2 * 1 = 24

Now, you must be thinking, where is the loop? How it’s iterating and getting data?

When I’ve called fact(4) it went into the function and got fact(3) and then it went into fact(3) and got fact(2)... .. and so on. Finally, it went to fact(0) and got 1 from the base case.
Then it started returning the value to fact(1), fact(2)... .. and so on, that’s why finally fact(4) got 6 from fact(3).

Discussion (2)

Collapse
ryan1 profile image
ryan

Unlike Python, PHP will let you recurse until you get a segmentation fault. So be careful :)

Collapse
evgeniir profile image
Evgeniy • Edited

Notice that PHP doesn't do tail call optimization, so use it carefully.