ejemplos - ¿PHP optimiza la recursividad de cola?

recursividad de cola en c

Question

Escribí un pequeño fragmento de código que creo que debería haber tenido éxito si se optimizaba la recursividad de la cola, sin embargo, explotó la pila. ¿Debo concluir que PHP no optimiza la recursividad de cola?

function sumrand($n,$sum) {
    if ($n== 0) {
        return $sum;
    }
    else {
        return (sumrand($n-1,$sum+rand(0,1)));
    }
}
echo sumrand(500000,0)."/n";

Answer 1

Es posible llamar funciones recursivas en PHP. Sin embargo, evite las llamadas a funciones / métodos recursivos con más de 100-200 niveles de recursión, ya que puede destruir la pila y provocar la finalización del script actual.

http://php.net/manual/en/functions.user-defined.php

Parece una suposición segura de que no lo es.

Answer 2

Aquí están los códigos de operación generados para eso (lo siento por la extraña representación):

Global
-------------------------------------------------------------------------------
BCDCAC 0003: NOP                  ()
BCDD24 0012: SEND_VAL             (CONST: "500000")
BCDD9C 0012: SEND_VAL             (CONST: NULL)
BCDE14 0012: DO_FCALL             (CONST: "sumrand") -> VAR 0
BCDE8C 0012: CONCAT               (VAR 0, CONST: "/n") -> TMP_VAR 1
BCDF04 0012: ECHO                 (TMP_VAR 1)
BCDF7C 0014: RETURN               (CONST: "1")

Functions
-------------------------------------------------------------------------------
sumrand (17 op)
BCFABC 0003: RECV                 (CONST: "1") -> CV 0 ($n)
BCFB34 0003: RECV                 (CONST: "2") -> CV 1 ($sum)
BCFBAC 0004: IS_EQUAL             (CV 0 ($n), CONST: NULL) -> TMP_VAR 0
BCFC24 0004: JMPZ                 (TMP_VAR 0, &(BCFD18+6))
BCFC9C 0005: RETURN               (CV 1 ($sum))
BCFD14 0006: JMP                  (&(BD01C8+10))
BCFD8C 0008: INIT_FCALL_BY_NAME   (NULL, CONST: "sumrand")
BCFE04 0008: SUB                  (CV 0 ($n), CONST: "1") -> TMP_VAR 1
BCFE7C 0008: SEND_VAL             (TMP_VAR 1)
BCFEF4 0008: SEND_VAL             (CONST: NULL)
BCFF6C 0008: SEND_VAL             (CONST: "1")
BCFFE4 0008: DO_FCALL             (CONST: "rand") -> VAR 2
BD005C 0008: ADD                  (CV 1 ($sum), VAR 2) -> TMP_VAR 3
BD00D4 0008: SEND_VAL             (TMP_VAR 3)
BD014C 0008: DO_FCALL_BY_NAME     () -> VAR 4
BD01C4 0008: RETURN               (VAR 4)
BD023C 0010: RETURN               (CONST: NULL)

Entonces, no, ciertamente no parece ser así.

Answer 3

Es importante saber que PHP es un lenguaje de scripting escrito en C, por lo que las limitaciones de este tipo están destinadas a aparecer. La falta de optimización se muestra en el lenguaje C subyacente también:

http://rosettacode.org/wiki/Find_limit_of_recursion

Como puede ver, PHP no es el único lenguaje que no maneja las cosas con gracia.

Recomiendo usar Erlang y el puente MyPeb PHP / Erlang para una verdadera solución a un problema como este.