Funções PHP recursivas anônimas

197

É possível ter uma função PHP recursiva e anônima? Esta é minha tentativa de fazê-lo funcionar, mas não passa o nome da função.

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

Também sei que essa é uma maneira ruim de implementar fatorial, é apenas um exemplo.

Kendall Hopkins
fonte
Eu não tenho o PHP 5.3.0 para verificar, mas você tentou usar global $factorial?
Kennytm 19/03/10
5
(nota de rodapé) um Lamba é uma função anônima, enquanto o acima é um fechamento.
19710 Gordon
1
Lambdas e Encerramentos não são mutuamente exclusivos. De fato, algumas pessoas acreditam que um fechamento deve ser lambda para que seja um fechamento (função anônima). Por exemplo, em Python, você deve dar um nome à função primeiro (dependendo da versão). Como você deve dar um nome a ele, não é possível incorporá-lo e alguns diriam que o desqualifica de ser um fechamento.
Adam Gent
1
print $factorial( 0);
nickb

Respostas:

356

Para que funcione, você precisa passar $ fatorial como referência

$factorial = function( $n ) use ( &$factorial ) {
    if( $n == 1 ) return 1;
    return $factorial( $n - 1 ) * $n;
};
print $factorial( 5 );
Derek H
fonte
isso é estranho, os objetos bc sempre devem ser passados ​​por referência e depois. funções são objetos ...
ellabeauty
25
@ellabeauty no momento em que $ fatorial é passado, ele ainda é nulo (não definido), é por isso que você deve passar por referência. Esteja ciente de que, se você modificar o fatorial $ antes de chamar a função, o resultado será alterado à medida que for passado por referência.
Marius Balčytis
9
@ellabeauty: Não, você entende completamente errado. Tudo sem &é por valor. Tudo com &é por referência. "Objetos" não são valores no PHP5 e não podem ser atribuídos ou transmitidos. Você está lidando com uma variável cujo valor é uma referência a objeto. Como todas as variáveis, ele pode ser capturado por valor ou por referência, dependendo da existência de um &.
Newacct
3
Mente fundida! Muito obrigado! Como eu não sabia disso até agora? A quantidade de aplicativos que tenho para funções anônimas recursivas é enorme. Agora posso finalmente percorrer estruturas aninhadas em layouts sem ter que definir explicitamente um método e manter todos os meus dados de layout fora das minhas classes.
Dieter Gribnitz
Como o @barius disse, cuidado ao usá-lo no foreach. $factorialserá alterado antes da função ser chamada e poderá resultar em comportamento estranho.
stil
24

Sei que essa pode não ser uma abordagem simples, mas aprendi sobre uma técnica chamada "correção" em linguagens funcionais. A fixfunção de Haskell é conhecida mais geralmente como o combinador Y , que é um dos combinadores de ponto fixo mais conhecidos .

Um ponto fixo é um valor inalterado por uma função: um ponto fixo de uma função f é qualquer x tal que x = f (x). Um combinador de ponto fixo y é uma função que retorna um ponto fixo para qualquer função f. Como y (f) é um ponto fixo de f, temos y (f) = f (y (f)).

Essencialmente, o combinador Y cria uma nova função que aceita todos os argumentos do original, além de um argumento adicional que é a função recursiva. Como isso funciona é mais óbvio usando a notação ao curry. Em vez de escrever argumentos entre parênteses ( f(x,y,...)), escreva-os após a função: f x y .... O combinador Y é definido como Y f = f (Y f); ou, com um único argumento para a função recorrente Y f x = f (Y f) x,.

Desde o PHP não automaticamente caril funções, é um bocado de um hack para fazer fixo trabalho, mas eu acho que é interessante.

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

Observe que isso é quase o mesmo que as soluções simples de fechamento postadas por outras pessoas, mas a função fixcria o fechamento para você. Os combinadores de ponto fixo são um pouco mais complexos do que usar um fechamento, mas são mais gerais e têm outros usos. Embora o método de fechamento seja mais adequado para PHP (que não é uma linguagem extremamente funcional), o problema original é mais um exercício do que para produção, portanto o combinador Y é uma abordagem viável.

Kendall Hopkins
fonte
10
Vale a pena notar que call_user_func_array()é lento como o Natal.
Xeoncross
11
@Xeoncross Ao contrário do resto do PHP, que está estabelecendo o recorde de velocidade terrestre? : P
Kendall Hopkins
1
Observe que agora você pode (5.6+) usar a descompactação de argumentos em vez de call_user_func_array.
Fabian Sa
@KendallHopkins por que esses argumentos adicionais array_unshift( $args, fix($func) );? Args já está carregado com os parâmetros e a recursão real é feita pelo call_user_func_array (), então o que essa linha faz?
Eu quero respostas
5

Embora não seja para uso prático, a extensão no nível C mpyw-junks / phpext-callee fornece recursão anônima sem atribuir variáveis .

<?php

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

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

Nas versões mais recentes do PHP, você pode fazer isso:

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

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

Isso pode levar a um comportamento estranho.

jgmjgm
fonte
0

Você pode usar o Y Combinator no PHP 7.1+ como abaixo:

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

Brinque com ele: https://3v4l.org/7AUn2

Códigos-fonte de: https://github.com/whitephp/the-little-phper/blob/master/src/chapter_9.php

Lei Fan
fonte
0

Com uma classe anônima (PHP 7+), sem definir uma variável:

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