Code auditing

All the recursive Functions in PHP

Posted on by dams

All the recursive Functions in PHPAll the recursive Functions in PHP

A recursive function is a function that calls itself, in order to solve a problem. This type of function is often used in situations where a problem can be broken down into smaller, similar yet smaller problems. The function keeps calling itself with modified arguments until a base case is reached, at which point the function stops calling itself and starts returning values. So, do we know all the recursive functions in PHP?

In this post, we are going to dive into the various shape that recursive PHP functions can take. This starts with the classic hard-coded recursive functions and methods; the extended indirect recursives functions; the elusive recursive closures and arrow functions; and finally, a sneaky abstracted recursive function.

Who knew that recursive functions could be so metamorphic!

Recursives functions

Recursive functions are the simplest form. It is a function that contains a call to itself. Classically, it is presented to calculate factorials: n!, read n factorial: factorial is the product of all integers between 1 and n, included. With recursion, it looks like this:

<?php

function factorial(int $n) : int {
  if ($n <= 1) { return 1; }
  return $n * factorial($n - 1);
}

print factorial(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

To calculate the factorial 4, the function makes the product between 4 and the factorial of 3. In turn, this factorial is calculated with the value of factorial 2; this cycle stops when factorial() reach 1 where it returns 1: that is the base case.

The recursion is based on the call to self: you can see the factorial call, inside the body of the same factorial function.

It is also important to note that this self call should be controlled by a condition: the condition’s role is to prevent the infinite loop by skipping the self call in specific situations. Here, a lesser factorial is calculated, unless it reaches 1 or less. Then, it unconditionally returns 1.

Recursive methods

Recursive methods are very close to recursive functions. One need a call to self, and, using the $this pseudo-variable, it is easy to find a suitable object for that call. The previous factorial function becomes the following:

<?php

class Factorial {
    function calculate(int $n) : int {
        if ($n <= 1) { return 1; }
        return $n * $this->calculate($n - 1);
    }
}

$factorial = new Factorial();
print $factorial->calculate(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Recursive distributed methods

Using $this is not the only possibility to make a recursive call. The previous code may skip the usage of $this by relying on a different object to propagate the calls.

<?php

class Factorial {
    function calculate(int $n) : int {
        if ($n <= 1) { return 1; }

        $that = new self();
        return $n * $that->calculate($n - 1);
    }
}

$factorial = new Factorial();
print $factorial->calculate(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Our initial definition of recursion, based on the self call, still applies. The above code is a recursive function, since the Factorial::calculate()calls itself. Yet, this is called on different objects each time, so it is also a bit different.

We have not been able to find an actual usage of such notion of recursion. Yet, it is intriguing to discover.

Indirect recursive functions

The functions we have presented so far are directly recursive: they directly call themselves. By extension, there are also indirectly recursive functions. The main difference is that they call different functions, that call them back, eventually.

<?php

function even(int $i) {
    return $i * odd($i - 1);
}

function odd(int $i) {
     if ($i === 1) { return 1;} 
   return $i * even($i - 1);
}

$n = 4;
if ($n % 2) {
    print even($n); // not used here
} else {
    print even($n); // 4! = 1 * 2 * 3 * 4 = 24
}

?>

In this code, the factorial is now spread across two distinct functions. One of the function process the odd numbers, and the other process the even ones. Since there are little checks on the initial values, it is important to choose the initial call well. This is not practical, but it illustrates the case of indirect recursion.

When processing the 4 factorial, first the even() function is call, which calls odd(), then even() again, then odd() and finally, everything is multiplied.

This illustration is an indirect recursion of level 2: levels may be increased arbitrarily, and there is no real limit to the number of functions in that circle of calls.

Indirect recursion is very rare in practice. It is a tricky and unstable structure, and quite difficult to get right. Still, it happens by simple organic growth, when methods calls each other until one finally calls again the first one, and triggers an infinite loop. Hopefully, this is detected early in development phase.

Recursive Closures

Functions and methods may be recursive with a simple call to oneself. This becomes a challenge with closures, as they are anonymous: they do not have a name, which could have been used to call itself. This is quite a challenge, and still, one that PHP can raise to.

<?php

$factorial = function (int $n) use (&$factorial)  : int {
        if ($n <= 1) { return 1; }
        return $n * $factorial($n - 1);
};

print $factorial(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Without a name, a closure has to be called with a variable that holds itself. So, to be recursive, a closure must receive a variable that contains itself. This is the role of the $factorial variable in the use clause. It is later used in the body to call onself.

One detail is the & reference, added to the factorial. Indeed, it is necessary here, and the closure won’t work without it. Without it, it yields the error Undefined variable $factorial.

While this looks strange, it is a normal phenonemon. The closure is build first, then assigned to the variable $factorial. The closure collects some variables from the current scope with the clause use, and include them in its own scope. Here, the $factorial variable is on the left side of the assignation, so it will be created after the closure itself. Hence, it is not available to collect when the closure is being defined.

Since the closure must include itself, the reference is necessary. The reference forces PHP to create the variable $factorial, without content (or NULL); it also keeps a handle to that variable. Later, after the closure definition, the closure is assigned to the $factorial, which leads it to be included in the closure.

If you create the variable $factorial before the closure, but do not use a reference on it, it will keep its previous value and is not injected in the closure. This doesn’t work.

Recursive closure with parameter

It is also possible to use the parameters to inject the closure and make it recursive. This time, no need to use a reference. On the other hand, one need to add the closure to all calls. The repetition is valid and a bit surprising to read.

<?php

$factorial = function (int $n, $factorial) : int {
        if ($n <= 1) { return 1; }
        return $n * $factorial($n - 1, $factorial);
};

print $factorial(4, $factorial); // 4! = 1 * 2 * 3 * 4 = 24

?>

Recursive Arrow Functions

The challenge is up one notch with recursive arrow functions. The trick now is that there is no more use clause, so it is not possible to make a reference that is filled with the arrow function itself. In fact, it is not possible to make a reference to the arrow function, since it is actually a Closureobject, and is a reference itself.

<?php

// Parse error: syntax error, unexpected token "fn" 
$factorial = &fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);

?>

In the code above, PHP cannot differentiate between the arrow function returning a reference, or $factorial being assigned a reference to the arrow function.

When the $factorial variable is created before the arrow function, then the arrow function collects its previous value: this is not the recursive arrow function. In the code below, the arrow function uses the integer 1, which is available before the definition of the arrow function.

<?php

$factorial = 1;
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);

//Fatal error: Uncaught Error: Value of type int is not callable

?>

One advantage of the arrow function over the Closure (cf previous sections), is that the arrow function only checks the content of the variable at execution time. So, it is possible to repeat the definition of the arrow function, and make it usable for the factorial problem. Of, course, there is a catch:

<?php

$factorial = 1;
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);

print $factorial(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

With each repetition, $factorial is able to make an extra call to a previous copy of itself. So, to calculate 4!, the arrow function definition needs to be duplicated 4 times. This leads to an (almost) recursive indirect function of level 4, although the last arrow function actually dies and shall not be used.

In the end, the only solution for recursive arrow functions is to use the argument syntax.

<?php

$factorial = fn (int $n, $factorial) : int => $n <= 1 ? 1 : $n * $factorial($n - 1, $factorial);

print $factorial(4, $factorial); // 4! = 1 * 2 * 3 * 4 = 24

?>

Abstracted recursive functions

Let’s finish by looping back to our initial definition of a recursive function : this was a function that calls itself. We managed to make recursive versions of all types of PHP functions. Now let’s look at the last code (above), with a slight change:

<?php

$factorial = fn (int $n, $foo) : int => $n <= 1 ? 1 : $n * $foo($n - 1, $foo);

print $factorial(4, $factorial); // 4! = 1 * 2 * 3 * 4 = 24

?>

Once the name of the parameter $factorialbecomes $foo, the recursive nature of the arrow function evaporates: it is not as obvious as previously. Indded, we could inject a different arrow function when calling it, and that would make the $factorial arrow function not recursive : on the other hand, its parameter $foo would be.

<?php

$factorial = fn (int $n, $foo) : int => $n <= 1 ? 1 : $n * $foo($n - 1, $foo);

// $factorial is not recursive
// foo() might be recursive
print $factorial(4, foo(...)); // 4! = 1 * 2 * 3 * 4 = 24

?>

When using a callable parameter, the call $factorial($x, $factorial) and the method definition that contains $factorial($x, $factorial) are needed to ensure that the function is recursive. Only one of them is not sufficient to make a recursive function.

In the initial examples, with named functions and methods, the hardcoded nature of the call makes it a sure characteristics to know these are recursive. With anonymous structures such as closures and arrow functions, the usage of these functions is also important to take into account. Otherwise, their recursive nature is mererly an abstract notion.

A Recursive Zoo in PHP

All the recursive functions in PHP makes quite a large zoo :

  • recursive functions
  • recursive methods
  • recursive closures
  • recursive arrow functions
  • indirect recursive functions
  • abstract recursive functions

It is interesting to realize how varied and complex the humble recursive function are in PHP. They do provide challenges with anonymous functions, distributed and indirect recursive functions and they even include call time parameters to be part of their own definition. Yet, they are a staple of the PHP world, with 44% of any projects using them.

And remember, that recursivity is up to the name of PHP itself!