Оптимизирует ли PHP хвостовую рекурсию? - PullRequest
Новая
       6

Оптимизирует ли PHP хвостовую рекурсию?

30 голосов
/ 30 мая 2011

Я написал небольшой фрагмент кода, который, по моему мнению, должен был бы быть успешным, если бы хвостовая рекурсия была оптимизирована, однако она взорвала стек.Должен ли я сделать вывод, что PHP не оптимизирует хвостовую рекурсию? 

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

Ответы [ 3 ]

29 голосов
/ 30 мая 2011

Вот сгенерированные коды операций для этого (извините за странное представление): 

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)

Так, нет, это, конечно, не так.

13 голосов
/ 30 мая 2011

В PHP можно вызывать рекурсивные функции. Однако избегайте рекурсивных вызовов функций / методов с более чем 100-200 уровнями рекурсии, поскольку это может разбить стек и вызвать завершение текущего сценария.

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

Похоже на безопасное предположение, что это не так.

0 голосов
/ 22 января 2015

Важно знать, что PHP является языком сценариев, написанным на C, поэтому ограничения такого рода обязательно появятся. Отсутствие оптимизации показывает и в базовом языке C:

http://rosettacode.org/wiki/Find_limit_of_recursion

Как видите, PHP - не единственный язык, который не справляется со всеми изящно.

Я рекомендую использовать Erlang и мост MyPeb PHP / Erlang для истинного решения такой проблемы.

...