Does PHP optimize tail recursion?
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.
Does Tail Recursion will be an optimization in php
The second script is faster because it recurses fewer total times, not because it uses tail recursion.
(The first script calls itself twice at each level. The second script only calls itself once at each level. As such, the second script simply ends up doing far less work than the first one.)
Optimizing a Recursive Method In PHP
See if you can use tail recursion rather than call-based recursion. Some rewriting may be required but a cursory looks says it is fine to do.
Tail recursion is great for a subset of recursive functions, and good practice to spot when loops can replace recursion, and how to rewrite.
Saying that, I don't know what the overhead inside PHP is of the call. Might just be one return-pointer type setup rather than a real stack wind.
Turns out about the same. Does PHP optimize tail recursive calls out itself?
Here is my rewrite, but beware, my brain is currently sleep deprived!
protected function compilePhrase($data, $currentIndex, $depth){
/* Loop until break condition */
while(true) {
if (!empty($data)){
if ($depth >= $this->phraseStart){
$this->addDataCount($data, $depth);
}
if ($depth < $this->phraseDepth){
$currentIndex = $currentIndex + 1;
// A test here might be better than the !empty($data)
// in the IF condition. Check array bounds, assuming
// array is not threaded or anything
$data .= ' '.$this->dataArray[$currentIndex];
$depth += 1;
}else{
break;
}
}else{
break;
}
}
/* Finish up here */
return($this->dataArray);
}
Optimizing a non-tail-recursive function
This code is untested, but from the top of my head, the iterative function should look something like this:
function render($index){
$stack = array();
array_push($index);
$pre = '';
$post = '';
while(!empty($stack)){
$idx = array_pop($stack);
foreach($things[$idx] as $key => $value){
$pre .= '<1>';
$spost = '';
if(isset($data['id'])){
$pre .= '<2 class="wrap">';
$spost .= '</2>';
$stack[] = $things[$data['id']];
}
$spost .= '</1>';
$post .= $spost;
}
}
return $pre . $post;
}
Tail Recursion Slower Than Normal Recursion in PHP?
I took your code and modified it slightly for running on the command line (converted br's to newlines, tweaked the output format). Also, I changed it so that benchmark is run for 25 iterations instead of just one:
<?php
foreach (range(1, 25) as $iteration) {
benchmark($iteration);
}
function benchmark($iteration)
{
$n = 10;
$multiplier = 10000;
$functions = array('factorial_recursive', 'factorial_tailRecursive');
echo "\nIteration {$iteration}:\n";
foreach ($functions as $function) {
$start = microtime(true);
echo $function . "\n";
echo $function($n) . "\n";
echo ($multiplier * (microtime(true) - $start)) . "\n\n";
}
}
function factorial_recursive($n)
{
if ($n == 1) {
return $n;
}
return $n * factorial_recursive($n - 1);
}
function factorial_tailRecursive($n, $result = 1)
{
if ($n == 1) {
return $result;
}
return factorial_tailRecursive($n - 1, $result * $n);
}
Here is my php cli version:
$ php --version
PHP 5.3.10-1ubuntu3.4 with Suhosin-Patch (cli) (built: Sep 12 2012 19:00:43)
Copyright (c) 1997-2012 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2012 Zend Technologies
with Xdebug v2.1.0, Copyright (c) 2002-2010, by Derick Rethans
Here are the results of my 25 iterations:
$ php ./benchmark.php
Iteration 1:
factorial_recursive
3628800
0.46014785766602
factorial_tailRecursive
3628800
0.33855438232422
Iteration 2:
factorial_recursive
3628800
0.26941299438477
factorial_tailRecursive
3628800
0.26941299438477
Iteration 3:
factorial_recursive
3628800
0.27179718017578
factorial_tailRecursive
3628800
0.2598762512207
Iteration 4:
factorial_recursive
3628800
0.26941299438477
factorial_tailRecursive
3628800
0.2598762512207
Iteration 5:
factorial_recursive
3628800
0.28848648071289
factorial_tailRecursive
3628800
0.28848648071289
Iteration 6:
factorial_recursive
3628800
0.27894973754883
factorial_tailRecursive
3628800
0.27894973754883
Iteration 7:
factorial_recursive
3628800
0.29087066650391
factorial_tailRecursive
3628800
0.2598762512207
Iteration 8:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.25033950805664
Iteration 9:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.2598762512207
Iteration 10:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.24795532226562
Iteration 11:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.27894973754883
Iteration 12:
factorial_recursive
3628800
0.27894973754883
factorial_tailRecursive
3628800
0.27894973754883
Iteration 13:
factorial_recursive
3628800
0.2598762512207
factorial_tailRecursive
3628800
0.25033950805664
Iteration 14:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.27179718017578
Iteration 15:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.24795532226562
Iteration 16:
factorial_recursive
3628800
0.24080276489258
factorial_tailRecursive
3628800
0.25033950805664
Iteration 17:
factorial_recursive
3628800
0.27179718017578
factorial_tailRecursive
3628800
0.25033950805664
Iteration 18:
factorial_recursive
3628800
0.24080276489258
factorial_tailRecursive
3628800
0.25033950805664
Iteration 19:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.25033950805664
Iteration 20:
factorial_recursive
3628800
0.25033950805664
factorial_tailRecursive
3628800
0.2598762512207
Iteration 21:
factorial_recursive
3628800
0.24795532226562
factorial_tailRecursive
3628800
0.23841857910156
Iteration 22:
factorial_recursive
3628800
0.30040740966797
factorial_tailRecursive
3628800
0.29087066650391
Iteration 23:
factorial_recursive
3628800
0.30994415283203
factorial_tailRecursive
3628800
0.26226043701172
Iteration 24:
factorial_recursive
3628800
0.29087066650391
factorial_tailRecursive
3628800
0.32186508178711
Iteration 25:
factorial_recursive
3628800
0.27894973754883
factorial_tailRecursive
3628800
0.30040740966797
Looking at these results, I'd have to say the difference is negligible, too close to call. They're effectively identical in runtime, at least in terms of Big-O.
How can I make this function tail recursive?
This would not be an example of tail recursion because computation is still being done in the earlier recursive calls AFTER the value is return. Consider the example provided in a previous StackOverflow post (What is tail recursion?). In this case, the ".=" operator would complete a concatenation and THEN return the result in the function.
To make this tail recursive you would want to modify your code print the 'output' variable prior to making the recursive call
Does array_walk_recursive use tail call optimization?
Short answer, no :)
See also: https://github.com/php/php-src/blob/master/ext/standard/array.c#L1097
What is tail recursion?
Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).
Here is a simple JavaScript implementation that uses recursion:
function recsum(x) {
if (x === 0) {
return 0;
} else {
return x + recsum(x - 1);
}
}
If you called recsum(5), this is what the JavaScript interpreter would evaluate:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.
Here's a tail-recursive version of the same function:
function tailrecsum(x, running_total = 0) {
if (x === 0) {
return running_total;
} else {
return tailrecsum(x - 1, running_total + x);
}
}
Here's the sequence of events that would occur if you called tailrecsum(5), (which would effectively be tailrecsum(5, 0), because of the default second argument).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.
Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it.
Are algorithm benchmarks in PHP pointless?
It's absolutely not pointless to benchmark algorithms in a scripting language. After doing the benchmarks, which implementation of factorial would you use in PHP? (assuming that you couldn't use the builtin one for some reason.)
It is fairly pointless to benchmark in a language that has significantly different features than the one that you want to implement the algorithm in though. Here, the relative cost of function calls and if statements in PHP is skewing the results significantly (or this is my best guess anyways). If you are careful to understand why this is happening and avoid it, it can still be fruitful though: differences will be more exaggerated as you noticed. It comes down to if it's easier to write it in the target language or work around the differences.
A simple calculation of complexity of the algorithm should be enough to decide which one to use, or at least narrow down the selections.
As Mike Axiak points out in the comments, you are not even testing different algorithms here, you are testing two different implementations of the same algorithm: keep a running product over i from n to 1. Doing this in a different language than the target is almost always pointless.
Related Topics
How to Convert Object into String in PHP
How Do Check If a PHP Session Is Empty
PHP Rename Array Keys in Multidimensional Array
PHP Session Ids -- How Are They Generated
How to Implement a Decorator in PHP
How to Determine If Pdo Is Enabled in PHP
"Class Xxx Is Not a Valid Entity or Mapped Super Class" After Moving the Class in the Filesystem
How to Set a Maximum Size Limit to PHP Curl Downloads
PHP Get All Arguments as Array
Google Calendar API Service Account Error
Assets Not Referencing to Public Folder (Laravel)
Send Checkbox Value in PHP Form
Regular Expression and Forward Slash
How to Detect When a User Has Successfully Finished Downloading a File in PHP
Aggregated Query Without Group By
How to Post Button Value to PHP