Skip to Main Content
×
Freshbooks
Official App
Free – Google Play
Get it
FreshBooks is Loved by American Small Business Owners
FreshBooks is Loved by Canadian Small Business Owners
FreshBooks is Loved by Small Business Owners in the UK
Dev Blog

Comparative Infinite Recursion

by Taavi 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). smile 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