PHP优化尾递归吗？

Question

我写了一小段代码，如果尾递归被优化，则应该成功，但它却导致堆栈溢出。我是否应该得出结论：PHP不会优化尾递归？

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

- Max

---

PHP是一种解释性语言。这类语言很少包含超过微不足道的优化。 - Rick James

Answer 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, &(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)

所以，不，显然并非如此。

- rid

Answer 2

可以在PHP中调用递归函数。但是要避免递归函数/方法调用超过100-200个递归层次，因为它可能会崩溃堆栈并导致当前脚本的终止。看起来这不是一个安全的假设。http://php.net/manual/en/functions.user-defined.php。

- deceze

---

编程语言有堆栈限制不是很常见吗？ - hakre

不仅仅是 PHP，几乎在任何语言中，编写不良的递归函数都会遇到相同的问题 :) 如果支持尾递归，则可以改变这一点。 - Ja͢ck

关于栈限制，我认为答案涉及到尾递归的含义。虽然编程语言有栈限制，但是尾递归会被优化成非递归跳转，因此不应该耗尽栈。因此，提到递归深度的限制实际上意味着没有尾递归。 - RonaldBarzell

@user 当条件为真时，人们会期望在上面的段落中指出尾递归的特殊情况。由于没有提到，可以安全地假设PHP没有针对它的特殊情况。 - deceze

@RonaldBarzell所说的“尾递归被优化为非递归跳转，因此不应该耗尽堆栈”是正确的，但并不是每个递归调用都是尾递归。因此，“它提到递归深度的限制”并不意味着编译器/解释器不会优化尾递归。 - Arnial

Answer 3

了解PHP是一种用C语言编写的脚本语言，因此这种限制必然会出现是很重要的。优化不足也反映在底层的C语言中：

http://rosettacode.org/wiki/Find_limit_of_recursion

正如您所见，PHP并不是唯一不能优雅地处理事情的语言。

我建议使用Erlang和MyPeb PHP/Erlang桥接来解决这类问题。

- Carl McDade

---

这不是实现的方式。特别是PHP只是字节码解释，而不是线程编译成C。 - Xwtek