Skip to Main Content
Official App
Free – Google Play
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 !
  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 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 -r "function f(){f();}f();"
Segmentation fault

Dies an untimely death, because :

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 -e "sub f{&f;}&f;"

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 -c "def 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 . See below for alternatives…


$ ruby -e "def 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 , , , etc. Even better, you can write your own language that supports tail call optimization (take a look at the last chapter of , and section in particular). However, since choosing (or writing) a different language is not always feasible, people are always coming up with 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:

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
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
def f(x):
if x == 1: return 1
return x + f(x-1)
f(1000) # maximum recursion depth exceeded
def f(x)
x == 1 ? x : x + f(x-1)
puts f(1)
puts f(10)
puts f(100)
puts f(1000)
puts f(10000) # stack level too deep
Грузия туры