I'm working on a side project, naturally in PHP (v4.4.1 to be specific). There's a lot of string parsing, and regex just wasn't able to handle it. When it worked, it would take 30+ seconds; often it timed out. I went and wrote some tail-recursive functions that would do the parsing, but much faster (it works about 90% of the time and load times take 2-3 seconds).

Unfortunately, PHP doesn't work well with recursion. For one, there's no real good way to release memory, so it's easy to use up all the available memory quickly. Oh well, so be it. That's how the language is built.

But there's another problem. It seems that after a few thousand recursive calls, PHP gives up the ghost. To be fair, a few thousand recursive calls isn't a terribly small number, but what it does to PHP is strange.

For example:

<?php
error_reporting(E_ALL); /* Lets be as fair as possible, if there's an error, we want to know */

function a($v) {
if($v>10000) { exit(); } /* This recursive function *will* stop */
echo $v . '<br />';
a($v+1);
}

a(0);
?>

Running this code (as I said, I'm using PHP4.4.1 here) produces:

0
1
2
3
...
3769
3770
3771
37

That's it. It doesn't even echo 3772 entirely, so it doesn't seem that the call stack is just reaching some maximum value and not letting the function call go through. It just dies. It always stops at '37', right after '3771'.

Weird.

In case you're wondering, I'm going to rewrite the recursion to use a while loop. That'll solve the speed issues, and the memory issues, and the magic recursion-stack-call issues.

Edit: The while loop did work, and it seems just as fast. It's not as appealing to the Computer Scientist in me, but it does work correctly, and ultimately, that's what matters.

As an example of turning recursion into a while loop (converting recursion to iteration), here's the above code, rewritten.

<?php
error_reporting(E_ALL); /* Lets be as fair as possible, if there's an error, we want to know */

$v = 0;

while($v<10000) {
echo $v . '<br />';
a($v+1);
}
?>