Comparative Infinite Recursion

by Jaco on February 13, 2008

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