Menu
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"; 
667
Tail recursion is important to some high-level languages, especially functional and logic languages and members of the Lisp family. In these languages, tail recursion is the most commonly used way (and sometimes the only way available) of implementing iteration.
As a rule of thumb; tail-recursive functions are faster if they don't need to reverse the result before returning it. That's because that requires another iteration over the whole list. Tail-recursive functions are usually faster at reducing lists, like our first example.
The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space. Go, however, does not implement tail-call optimization, and you will eventually run out of memory.
Recursion is a fundamental concept in programming yet it trips up many programmers, sometimes even the experienced ones. But once you have understood the concept of recursion you might have also figured out that it is inefficient in terms of memory usage and performance.
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.
192
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.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
