A sample recursive php function producing excessive stack (from Common PHP)

0-recur.php

<?php

/*
I wanted to know if it pays off to refactor some recursive code, and 
if or not PHP does tail call optimization and i found this post:
http://commonphp.blogspot.com/2010/12/tail-call-optimization-in-php-53.html
A good place to check how much faster an itarative solution would be. 
I started with executing the functions.
Result: PHP does not do TCO. 
*/

function even($n) { 
    return $n == 0 ? true : odd($n - 1);
}

function odd($n) { 
    return $n == 0 ? false: even($n - 1);
}

echo even(15000000) ? 'Yep' : 'Nope'; 


/*

The result of this file beeing executed:

$ php recur.php
Speicherzugriffsfehler

or with xdebug

$ php 0-recur.php                                                      
PHP Fatal error:  Maximum function nesting level of '100' reached, aborting! in /home/amoebe/recur.php on line 8
PHP Stack trace:                                                                                                
PHP   1. {main}() /home/amoebe/recur.php:0                                                                      
PHP   2. even() /home/amoebe/recur.php:11                                                                       
PHP   3. odd() /home/amoebe/recur.php:4    
...

*/

1-trm-recur.php

<?php

/*
The next thing listed in
http://commonphp.blogspot.com/2010/12/tail-call-optimization-in-php-53.html
is a trampoline implemented in PHP. Pretty neat idea. 
However creating and calling closures for realizing CPS
feels very expensive. 
*/

function trampoline($func, $args) {
    $return = call_user_func_array($func, $args);
    while(is_callable($return)) {
        $return = $return();
    }
    return $return;
}

function even($n) {
    return $n == 0 ? true : function() use($n) { return odd($n - 1); };
}

function odd($n) {
    return $n == 0 ? false : function() use($n) { return even($n - 1); };
}

echo trampoline('even', array(15000000)) ? 'Yep' : 'Nope';

/*

The result of this file beeing executed:

$ time php 1-trm-recur.php
Yep
real    2m50.478s
user    1m24.893s
sys     1m15.065s


*/

2-it-recur.php

<?php
/*
So next thing I tried is rewriting these function
in an itarative manner, and it is indeed so much
faster (3 Minutes > 6 seconds). These are of course
very simple functions, were we don't save tons of
byes into stacks and caches to realize something
itarative. 

I think it pays off to refactor your recursive calls, 
at least if you want to cover (really) deep recursion. 
*/

function even($n) {
    $even=false;
    for (;$n>=0;$n--) {
        $even=!$even;
    }
    return $even;
}

function odd($n) {
    return even($n+1);
}

echo even(15000000) ? 'Yep' : 'Nope';


/*

The result of this file beeing executed:

$ time php 2-it-recur.php
Yep
real    0m6.636s
user    0m5.980s
sys     0m0.044s

*/

3-trm-chick-recur.php

<?php

/*
You could use a technique from chicken scheme implementation
to pass the continuation only every n times making real
unlimited recursion twice as fast. 
Unless there's not too much recursion, just do normal
recursive calls. 
If you get to a stck size of 50 (should be save)
you "flush" the stack by passing the continuation. 

If you use a small number here like n=5, you create a lot of
closures and it gets a little slower. 
Funny enough, if you turn this number up to n=1000, n=10000
 or so it will get slower again. Apparently for big stack
its managing produces much more overhead than closures. 
*/

define("MAX_STACK_SIZE",50);


function trampoline($func, $args) {
    $return = call_user_func_array($func, $args);
    while(is_callable($return)) {
        $return = $return();
    }
    return $return;
}

function even($n,$r=0) {
    if($r<MAX_STACK_SIZE) return $n == 0 ? true :  odd($n - 1, $r + 1);
    return $n == 0 ? true : function() use($n) { return odd($n - 1); };
}

function odd($n,$r=0) {
    if($r<MAX_STACK_SIZE) return $n == 0 ? true :  even($n - 1,$r + 1);
    return $n == 0 ? false : function() use($n) { return even($n - 1); };
}

echo trampoline('even', array(15000000)) ? 'Yep' : 'Nope';

/*

The result of this file beeing executed:

$ time php 3-trm-chick-recur.php
Yep
real    1m1.550s
user    0m31.502s
sys     0m26.162s


*/