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

ProgramBox

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

Post author:admin
Запись опубликована:23 апреля, 2023
Post category:Вопросы по программированию

#php #recursion #tail-recursion

#php #рекурсия #хвостовая рекурсия

Вопрос:

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

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

Ответ №1:

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

 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, amp;(BCFD18 6))
BCFC9C 0005: RETURN               (CV 1 ($sum))
BCFD14 0006: JMP                  (amp;(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)

Итак, нет, это определенно так не кажется.

Ответ №2:

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

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

Кажется безопасным предположением, что это не так.

1. Разве это не обычное дело, когда язык программирования имеет ограничение по стеку?

2. @hakre Определенно не уникален для PHP, плохо написанная рекурсивная функция столкнется с теми же проблемами практически на любом языке 🙂 хвостовая рекурсия изменяет это (если поддерживается)

3. Что касается ограничения стека, я думаю, что ответ был в отношении того, что это означало для хвостовой рекурсии. Конечно, языки имеют ограничение стека, но хвостовая рекурсия оптимизирована для нерекурсивного перехода, поэтому она не должна исчерпывать стек. Итак, по сути, тот факт, что в нем упоминается ограничение глубины рекурсии, подразумевает отсутствие хвостовой рекурсии.

4. @user Несмотря на значение true, можно было бы ожидать, что в приведенном выше абзаце будет указан особый случай хвостовой рекурсии. Поскольку это не так, можно с уверенностью предположить, что в PHP для этого нет специального случая.

5. @RonaldBarzell «хвостовая рекурсия оптимизирована для нерекурсивного перехода, поэтому она не должна исчерпывать стек» это верно, но не каждый рекурсивный вызов является хвостовым рекурсивным. Итак, «тот факт, что в нем упоминается ограничение глубины рекурсии», не подразумевает, что компилятор / iterpreter не оптимизируют хвостовую рекурсию.

Ответ №3:

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

http://rosettacode.org/wiki/Find_limit_of_recursion

Как вы можете видеть, PHP — не единственный язык, который не обрабатывает вещи изящно.

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