¿PHP optimiza la recursividad de cola?

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?¿PHP 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";

Fuente

2011-05-30 Max

Éstos son los códigos de operación generados para que (lo siento por la representación extraña):

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)

tanto, no, ciertamente no lo parece.

Fuente

2011-05-30 02:37:34 rid

Es posible llamar a 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 que no lo es.

Fuente

2011-05-30 02:44:16 deceze

¿No es común que un lenguaje de programación tenga un límite de pila? – hakre

@hakre Definitivamente no exclusivo de PHP, una función recursiva mal escrita se ejecutará en los mismos problemas en prácticamente cualquier idioma :) Repetición de cola cambia eso (si es compatible) –

En cuanto al límite de la pila, creo que la respuesta fue con respecto a lo que esto destinado a la recursividad de la cola. Claro, los lenguajes tienen un límite de pila, pero la recursividad de cola se optimiza en un salto no recursivo, por lo que no debería agotar la pila. Entonces, en esencia, el hecho de que mencionaría un límite a la profundidad de recursión, implica que no se repita la cola. – RonaldBarzell

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 muestra en el lenguaje C subyacente también:

http://rosettacode.org/wiki/Find_limit_of_recursion

Como se puede ver PHP no es el único idioma 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.

Fuente

2015-01-22 08:25:13

¿PHP optimiza la recursividad de cola?

Respuesta

Cuestiones relacionadas