As you may know, I started at FreshBooks at the start of this year. You’ll see me posting random programming-related things as I hit them in my move from systems C programming into the world of PHP and web programming.

Yesterday I was merrily coding away, creating Cool New Features for you, our FreshBooks users. After adding 4 innocent lines of code, I started to see raw JavaScript instead of the beautifully formatted FreshBooks interface we all love. This led me through the following hoops:

1. There’s no trailing <script> tag in the page source. So that’s why I saw raw JavaScript.
2. Apache’s error.log showed dying processes!
3. Reconfiguring Apache to use only one child thread, I attached gdb and recreated it…and caught PHP dying of a segmentation fault!
4. At this point I think I’ve found a bug in PHP (since progams should never ever segfault).
5. Then I discovered I made the classic error of pasting-without-looking, and inadvertently created an infinite recursion!, and found a bug report that indicates that this is “working as designed” in PHP. *cough*

To wit, I proceeded to see how other scripting languages handle infinite recursion. Here are the results…

PHP

$ php -r “function f(){f();}f();”
Segmentation fault

Dies an untimely death, because each function invocation recursively calls execute():

In my opinion, a well-behaved program should NEVER segfault, because a segmentation is only rarely the first bad thing that’s happened (it’s just the most fatal one to the process in question). But let’s see if anyone else does better…

Perl

$ perl -e “sub f{&f;}&f;”
Killed

Runs the system out of memory (all 256MB RAM + 400MB swap in my Linux VMWare image). While this is horrible from a denial-of-service perspective, it’s easy to prevent by setting ulimit on the server processes. And it shows that Perl isn’t artificially limiting recursion depth; if you’ve got the RAM, you can go to infinity (almost).

Python

$ python -c “def f(): f()
f()”
Traceback (most recent call last):
  File “<string>”, line 2, in <module>
  File “<string>”, line 1, in f
…
RuntimeError: maximum recursion depth exceeded

YAY! A useful result. Of course it indicates that you may have problems recursing deeply. See below for alternatives…

Ruby

$ ruby -e “def f
  f()
end
f()”
-e:2:in `f’: stack level too deep (SystemStackError)
	from -e:2:in `f’
	from -e:4

Also an excellent, useful error message!

Tail Recursion

Of course, if you wanted to loop infinitely, you’d be much better off using a language that supports tail call optimization. Something like Scheme, Lua, Erlang, etc. Even better, you can write your own language that supports tail call optimization (take a look at the last chapter of Structure and Interpretation of Computer Programs, and section 5.1.4 in particular). However, since choosing (or writing) a different language is not always feasible, people are always coming up with creative solutions in languages that don’t support TCO!

For those with a practical bent

Not willing to give this up just yet, here’s a set of less artificial examples:

<?
//php
function f($x) {
	if ($x == 1) return 1;
	return ($x + f($x-1));
}
echo f(1) . "\n";
echo f(10) . "\n";
echo f(100) . "\n";
echo f(1000) . "\n";
echo f(10000) . "\n";
echo f(100000) . "\n"; // Segmentation fault
?>

#perl
sub f {
	my $x = shift;
	if ($x == 1) {return 1;}
	return ($x + f($x-1));
}
print(f(1) . "\n");
print(f(10) . "\n");
print(f(100) . "\n");
print(f(1000) . "\n");
print(f(10000) . "\n");
print(f(100000) . "\n");
print(f(1000000) . "\n");
print(f(10000000) . "\n"); # malloc: *** mmap(size=351752192) failed

#python
def f(x):
	if x == 1: return 1
	return x + f(x-1)

f(1)
f(10)
f(100)
f(1000) # maximum recursion depth exceeded

#ruby
def f(x)
	x == 1 ? x : x + f(x-1)
end
puts f(1)
puts f(10)
puts f(100)
puts f(1000)
puts f(10000) # stack level too deep