我写了一小段代码,我相信如果尾递归被优化,它应该会成功,但是它会炸毁堆栈。我应该总结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";
我写了一小段代码,我相信如果尾递归被优化,它应该会成功,但是它会炸毁堆栈。我应该总结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";
下面是所产生的操作码(对不起,怪表示):
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)
所以,不,它肯定似乎并非如此。
有可能在PHP中调用递归函数。但是,要避免递归函数/方法调用超过100-200递归级别,因为它可以粉碎堆栈并导致当前脚本的终止。
似乎是一个安全的假设,它不是。
知道PHP是用C语言编写的脚本语言很重要,所以这种限制必然会出现。缺乏优化的显示了底层的C语言也:
http://rosettacode.org/wiki/Find_limit_of_recursion
正如你可以看到PHP是不是不处理的东西摆好的唯一语言。
我推荐使用Erlang和MyPeb PHP/Erlang桥来解决这个问题。
编程语言是否有堆栈限制? – hakre 2012-10-10 02:12:52
@hakre绝对不是唯一的PHP,一个写得不好的递归函数几乎会在任何语言中遇到相同的问题:)尾递归改变(如果支持) – 2012-10-10 02:49:55
关于堆栈限制,我认为答案是关于这个意味着尾递归。当然,语言有堆栈限制,但是尾递归优化为非递归跳跃,所以它不应该耗尽堆栈。所以实质上,它会提到递归深度的限制,这意味着没有尾递归。 – RonaldBarzell 2012-11-30 14:02:46