38

I wrote a small piece of code that I believe should have succeeded if tail recursion was optimized, however it blew up the stack. Should I conclude PHP does not optimize tail recursion?

function sumrand($n,$sum) {
    if ($n== 0) {
        return $sum;
    }
    else {
        return (sumrand($n-1,$sum+rand(0,1)));
    }
}
echo sumrand(500000,0)."\n";
1
  • PHP is an interpretive language. Such languages rarely include more than trivial optimizations.
    – Rick James
    Aug 3 at 3:14

3 Answers 3

37

Here are the generated opcodes for that (sorry for the strange representation):

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)

So, no, it certainly doesn't seem so.

17

It is possible to call recursive functions in PHP. However avoid recursive function/method calls with over 100-200 recursion levels as it can smash the stack and cause a termination of the current script.

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

Seems like a safe assumption that it's not.

5
  • 1
    Isn't it common that a programming language has a stack limit?
    – hakre
    Oct 10, 2012 at 2:12
  • 6
    @hakre Definitely not unique to PHP, a poorly written recursive function will run into the same issues in practically any language :) tail recursion changes that (if supported)
    – Ja͢ck
    Oct 10, 2012 at 2:49
  • 1
    Regarding the stack limit, I think the answer was in regard to what this meant for tail recursion. Sure, languages have a stack limit, but tail recursion is optimized into a non-recursive jump, so it shouldn't exhaust the stack. So in essence, the fact that it would mention a limit to recursion depth, implies no tail recursion. Nov 30, 2012 at 14:02
  • 1
    @user While true, one would expect the special case of tail recursion to be pointed out in the above paragraph. Since it's not, it's safe to assume that PHP has no special case for it.
    – deceze
    Nov 30, 2012 at 14:06
  • @RonaldBarzell "tail recursion is optimized into a non-recursive jump, so it shouldn't exhaust the stack" that is true but not every recursive call is tail recursive. So "the fact that it would mention a limit to recursion depth" dosn't implies that complier/iterpreter don't optimize tail recursion.
    – Arnial
    Aug 10, 2016 at 12:02
-5

It is important to know that PHP is a scripting language written in C so limitations of this sort are bound to appear. The lack of optimization shows in the underlying C language also:

http://rosettacode.org/wiki/Find_limit_of_recursion

As you can see PHP is not the only language that does not handle things gracefully.

I recommend using Erlang and the MyPeb PHP/Erlang bridge for a true solution to a problem like this.

1
  • 1
    That's not how implementation works. Especially php is just bytecode-interpreted rather than thread-compiled to C.
    – Xwtek
    Feb 11, 2019 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.