Anonymous recursive PHP functions

Question

Is it possible to have a PHP function that is both recursive and anonymous? This is my attempt to get it to work, but it doesn't pass in the function name.

$factorial = function( $n ) use ( $factorial ) {
    if( $n <= 1 ) return 1;
    return $factorial( $n - 1 ) * $n;
};
print $factorial( 5 );

I'm also aware that this is a bad way to implement factorial, it's just an example.

Answer 1

In order for it to work, you need to pass $factorial as a reference

$factorial = function( $n ) use ( &$factorial ) {
    if( $n == 1 ) return 1;
    return $factorial( $n - 1 ) * $n;
};
print $factorial( 5 );

Answer 2

I know this might not be a simple approach, but I learned about a technique called "fix" from functional languages. The fix function from Haskell is known more generally as the Y combinator, which is one of the most well-known fixed point combinators.

A fixed point is a value that is unchanged by a function: a fixed point of a function f is any x such that x = f(x). A fixed point combinator y is a function that returns a fixed point for any function f. Since y(f) is a fixed point of f, we have y(f) = f(y(f)).

Essentially, the Y combinator creates a new function that takes all the arguments of the original, plus an additional argument that's the recursive function. How this works is more obvious using curried notation. Instead of writing arguments in parentheses (f(x,y,...)), write them after the function: f x y .... The Y combinator is defined as Y f = f (Y f); or, with a single argument for the recursed function, Y f x = f (Y f) x.

Since PHP doesn't automatically curry functions, it's a bit of a hack to make fix work, but I think it's interesting.

function fix( $func )
{
    return function() use ( $func )
    {
        $args = func_get_args();
        array_unshift( $args, fix($func) );
        return call_user_func_array( $func, $args );
    };
}

$factorial = function( $func, $n ) {
    if ( $n == 1 ) return 1;
    return $func( $n - 1 ) * $n;
};
$factorial = fix( $factorial );

print $factorial( 5 );

Note this is almost the same as the simple closure solutions others have posted, but the function fix creates the closure for you. Fixed point combinators are slightly more complex than using a closure, but are more general, and have other uses. While the closure method is more suitable for PHP (which isn't a terribly functional language), the original problem is more of an exercise than for production, so the Y combinator is a viable approach.

Answer 3

Although it is not for practial usage, The C-level extension mpyw-junks/phpext-callee provides anonymous recursion without assigning variables.

<?php

var_dump((function ($n) {
    return $n < 2 ? 1 : $n * callee()($n - 1);
})(5));

// 5! = 5 * 4 * 3 * 2 * 1 = int(120)

Answer 4

With an anonymous class (PHP 7+), without defining a variable:

echo (new class {
    function __invoke($n) {
        return $n < 2 ? 1 : $n * $this($n - 1);
    }
})(5);

Answer 5

In newer versions of PHP you can do this:

$x = function($depth = 0) {
    if($depth++)
        return;

    $this($depth);
    echo "hi\n";
};
$x = $x->bindTo($x);
$x();

This can potentially lead to strange behaviour.

Answer 6

You can use Y Combinator in PHP 7.1+ as below:

function Y
($le)
{return
    (function ($f) 
     {return
        $f($f);
     })(function ($f) use ($le) 
        {return
            $le(function ($x) use ($f) 
                {return
                    $f($f)($x);
                });
        });
}

$le =
function ($factorial)
{return
    function
    ($n) use ($factorial)
    {return
        $n < 2 ? $n
        : $n * $factorial($n - 1);
    };
};

$factorial = Y($le);

echo $factorial(1) . PHP_EOL; // 1
echo $factorial(2) . PHP_EOL; // 2
echo $factorial(5) . PHP_EOL; // 120

Play with it: https://3v4l.org/7AUn2

Source codes from: https://github.com/whitephp/the-little-phper/blob/master/src/chapter_9.php