PHP是否優化尾遞歸？

我寫了一小段代碼，我相信如果尾遞歸被優化，它應該會成功，但是它會炸燬堆棧。我應該總結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";

來源

2011-05-30 Max

下面是所產生的操作碼（對不起，怪表示）：

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)

所以，不，它肯定似乎並非如此。

來源

2011-05-30 02:37:34 rid

有可能在PHP中調用遞歸函數。但是，要避免遞歸函數/方法調用超過100-200遞歸級別，因爲它可以粉碎堆棧並導致當前腳本的終止。

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

似乎是一個安全的假設，它不是。

來源

2011-05-30 02:44:16 deceze

編程語言是否有堆棧限制？ – hakre 2012-10-10 02:12:52

@hakre絕對不是唯一的PHP，一個寫得不好的遞歸函數幾乎會在任何語言中遇到相同的問題:)尾遞歸改變（如果支持） – 2012-10-10 02:49:55

關於堆棧限制，我認爲答案是關於這個意味着尾遞歸。當然，語言有堆棧限制，但是尾遞歸優化爲非遞歸跳躍，所以它不應該耗盡堆棧。所以實質上，它會提到遞歸深度的限制，這意味着沒有尾遞歸。 – RonaldBarzell 2012-11-30 14:02:46

知道PHP是用C語言編寫的腳本語言很重要，所以這種限制必然會出現。缺乏優化的顯示了底層的C語言也：

http://rosettacode.org/wiki/Find_limit_of_recursion

正如你可以看到PHP是不是不處理的東西擺好的唯一語言。

我推薦使用Erlang和MyPeb PHP/Erlang橋來解決這個問題。

來源

2015-01-22 08:25:13

PHP是否優化尾遞歸？

回答

相關問題