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.

Solution 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 );

Solution 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.

Solution 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)

Comments

[kennytm]

I don't have PHP 5.3.0 to check but did you try using global $factorial?

[Gordon]

(sidenote) a Lamba is an anonymous function, while the above is a Closure.

[Adam Gent]

Lambdas and Closures are not mutually exclusive. In fact some people believe that a closure has to be lambda for it to be a closure (anonymous function). For example Python you sort of have to give the function a name first (depending on version). Because you have to give it a name you can't inline and some would say that disqualifies it from being a closure.

[nickb]

print $factorial( 0);

[Admin]

php Manual example

[Xeoncross]

It's worth noting that call_user_func_array() is slow as Christmas.

[Kendall Hopkins]

@Xeoncross As opposed to the rest of PHP which is setting the land speed record? :P

[ellabeauty]

that's weird bc objects should always be passed by reference, and anon. functions are objects...

[Marius Balčytis]

@ellabeauty in the time $factorial is passed, it is still null (not defined), that's why you have to pass it by reference. Be aware, that if you modify the $factorial before calling the function, the result will change as it's passed by reference.

[newacct]

@ellabeauty: No, you completely misunderstand it. Everything without & is by value. Everything with & is by reference. "Objects" are not values in PHP5 and cannot be assigned or passed. You are dealing with a variable whose value is an object reference. Like all variables, it can be captured by value or by reference, depending on whether there is an &.

[Dieter Gribnitz]

Mind Blown! Thanks a lot! How did I not know about this till now? The amount of application I have for recursive anonymous functions is huge. Now I can finally loop through nested structures in layouts without having to explicitly define a method and keep all my layout data out of my classes.

[stil]

Like @barius said, careful when using it in foreach. $factorial will be changed before function was called and it may result with strange behaviour.

[Fabien Sa]

Note, you can now (5.6+) use argument unpacking instead of call_user_func_array.

[I Want Answers]

@KendallHopkins why this additional arguments array_unshift( $args, fix($func) );? Args is already laden with the parameters, and the actual recursion is done by the call_user_func_array(), so what does that line do?