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.
Source: Tips4all
In order for it to work, you need to pass $factorial as a reference
ReplyDelete$factorial = function( $n ) use ( &$factorial ) {
if( $n == 1 ) return 1;
return $factorial( $n - 1 ) * $n;
};
print $factorial( 5 );
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.
ReplyDeleteA 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.
Try this (uses global):
ReplyDelete$factorial = function($n) {
global $factorial;
if ($n == 1) return 1;
return $factorial($n - 1) * $n;
};
or (using create_function and nowdoc)
$factorial = create_function('$n', <<<'EOL'
global $factorial;
if( $n == 1 ) return 1;
return $factorial($n - 1) * $n;
EOL
);