How does your favorite language handle deep recursion?

Question

I recently started learning Python and I was rather surprised to find a 1000 deep recursion limit (by default). If you set it high enough, about 30000, it crashes with a segmentation fault just like C. Although, C seems to go quite a lot higher.

(The Python folks are quick to point out that you can always convert recursive functions to iterative ones and that they're always faster. That's 100% true. It's not really what my question is about though.)

I tried the same experiment in Perl and somewhere around 10 million recursions it consumed all of my 4 gigs of ram and I used ^C to stop trying. Clearly Perl doesn't use the C stack, but it does use a ridiculous amount of memory when it recurses -- not terribly shocking considering how much work it has to do to call functions.

I tried in Pike and was completely surprised to get 100,000,000 recursions in about 2 seconds. I have no idea how it did that, but I suspect it flattened the recursion to an iterative process -- it doesn't seem to consume any extra memory while it does it. [Note: Pike does flatten trivial cases, but segfaults on more complicated ones, or so I'm told.]

I used these otherwise useless functions:

int f(int i, int l) { if(i<l) return f(i+1,l); return i; }

sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };

def f(i,l):
   if i<l:
     return f(i+1,l)
   return i

I'm very curious how other languages (e.g., PHP, Ruby, Java, Lua, Ocaml, Haskell) handle recursion and why they handle it that way. Additionally, please note whether it makes a difference if the function is "tail-recursive" (see comment).

Answer 1

PHP has a default limit of 100 before it dies:

Fatal error: Maximum function nesting level of '100' reached, aborting!

Edit: You can change the limit with ini_set('xdebug.max_nesting_level', 100000);, but if you go above about 1150 iterations PHP crashes:

[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.

Answer 2

According to this thread, around 5,000,000 with java, 1Gb RAM. (and that, with the 'client' version of the hotspot)

That was with a stack (-Xss) of 300Mo.

With a -server option, that could be increased.

Also one can try to optimize the compiler (with JET for instance) to reduce the stack overhead at each layer.

Answer 3

C#/.NET will use tail recursion in a particular set of circumstances. (The C# compiler doesn't emit a tailcall opcode, but the JIT will implement tail recursion in some cases.

Shri Borde also has a post on this topic. Of course, the CLR is continually changing, and with .NET 3.5 and 3.5SP1 it may have changed again with respect to tail calls.

Answer 4

Visual Dataflex will stack overflow.

Answer 5

"The Python folks are quick to point out that you can always convert recursive functions to iterative ones and that they're always faster"

This is true, but if it's really as easy as all that, why doesn't Python do it for me, so that my code can look as simple as possible? (I say this not to slam Python implementers, but because the answer explains the problem).

Recursion optimisations have been present in functional languages since, like, the 14th century or something. Haskell, CAML, Lisp implementations all typically convert at least tail recursive functions to iterations: you basically do this by spotting that it's possible, i.e. that the function can be rearranged such that no local variables other than the return value are used after the recursive call. One trick to make it possible if there's some work done to the recursed return value before return, is to introduce an additional "accumulator" parameter. In simple terms this means the work can effectively be done on the way "down" instead of on the way "up": search around for 'how to make a function tail-recursive' for details.

The actual details of turning a tail recursive function into a loop is basically to jigger with your call convention such you can "perform the call" simply by setting up the parameters and jumping back to the start of the function, without bothering to save all that stuff in scope that you know you won't ever use. In assembler terms, you don't have to preserve caller-saves registers if data-flow analysis tells you they're unused beyond the call, and the same goes for anything on the stack: you don't have to move the stack pointer on a call if you don't mind "your" bit of stack being scribbled over by the next recursion/iteration.

Contrary to how you paraphrased the Python folks, converting a general recursive function to an iteration is not trivial: for example if it's multiply-recursive then in a simple approach you'd still need a stack.

Memoization is a useful technique, though, for arbitrarily recursive functions, that you might like to look up if you're interested in the possible approaches. What it means is that each time a function is evaluated, you stick the result in a cache. To use this to optimize recursion, basically, if your recursive function counts "down", and you memoize it, then you can evaluate it iteratively by adding a loop that counts "up" calculating each value of the function in turn until you reach the target. This uses very little stack space provided that the memo cache is big enough to hold all the values you'll need: for instance if f(n) depends on f(n-1), f(n-2) and f(n-3) you only need space for 3 values in the cache: as you go up you can kick the ladder away. If f(n) depends on f(n-1) and f(n/2), you need lots of space in the cache, but still less than you'd use for stack in an unoptimised recursion.

Answer 6

In some non pathological cases (like your), (latest) Lua will use tail call recursion, ie. it will just jump without pushing data in stack. So the number of recursion loops can be almost unlimited.

Tested with:

function f(i, l)
    if i < l then
     return f(i+1, l)
    end
    return i
end

local val1  = arg[1] or 1
local val2  = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))

Also with:

function g(i, l)
    if i >= l then
     return i
    end
    return g(i+1, l)
end

and even tried cross-recursion (f calling g and g calling f...).

On Windows, Lua 5.1 uses around 1.1MB (constant) to run this, finishes in a few seconds.

Answer 7

Using the following in the F# interactive console, it ran in less than a second:

let rec f i l = 
  match i with 
  | i when i < l -> f (i+1) l
  | _ -> l

f 0 100000000;;

I then tried a straight translation i.e.

let rec g i l = if i < l then g (i+1) l else l

g 0 100000000;;

Same outcome but different compilation.

This is what f looks like in when translated to C#:

int f(int i, int l)
{
  while(true)
  {
    int num = i;
    if(num >= l)
      return l;
    int i = num;
    l = l;
    i = i + 1;
  }
}

g, however is translated to this:

int g(int i, int l)
{
  while(i < l)
  {
    l = l;
    i++;
  }
  return l;
}

It is interesting that two functions that are fundamentally the same are rendered differently by the F# compiler. It also shows that the F# compiler has tail-recursive optimization. Thus this should loop until i reaches the limit for 32-bit integers.

Answer 8

This is more of an implementation question than a language question. There's nothing stopping some (stoopid) C compiler implementor from also limiting their call stack to 1000. There are a lot of small processors out there that wouldn't have stack space for even that many.

(The Python folks are quick to point out that you can always convert recursive functions to iterative ones and that they're always faster. That's 100% true. It's not really what my question is about though.)

Perhaps they do say that, but this isn't quite correct. Recursion can always be converted to iteration, but sometimes it also requires manual use of a stack too. In those circumstances, I could see the recursive version being faster (assuming you are smart enough to make simple optimizations, like pulling unneeded declarations outside of the recursive routine). After all, the stack pushes surrounding procedure calls are a well bounded problem that your compiler should know how to optimize very well. Manual stack operations, on the other hand, are not going to have specialized optimization code in your compiler, and are liable to have all sorts of user-interface sanity checks that will take up extra cycles.

It may be the case that the iterative/stack solution is always faster in Python. If so, that's a failing of Python, not of recursion.

Answer 9

There is a way to improve upon the Perl code, to make it use a constant size stack. You do this by using a special form of goto.

sub f{
  if( $_[0] < $_[1] ){

    # return f( $_[0]+1, $_[1] );

    @_ = ( $_[0]+1, $_[1] );
    goto &f;

  } else {
    return $_[0]
  }
}

When first called it will allocate space on the stack. Then it will change its arguments, and restart the subroutine, without adding anything more to the stack. It will therefore pretend that it never called its self, changing it into an iterative process.

---

You could also use the Sub::Call::Recur module. Which makes the code easier to understand, and shorter.

use Sub::Call::Recur;
sub f{
  recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
  return $_[0];
}

Answer 10

I'm quite a fan of functional programming, and since most of those langauges implement tail call optimization, you can recurse as much as you like :-P

However, practically, I have to use a lot of Java and use Python a lot too. No idea what limit Java has, but for Python I had actually planned (but have not yet done it) to implement a decorator which would tail call optimize the decorated function. I was planning this not to optimize recursion, but mainly as an exercise in dynamically patching Python bytecode and learning more about Pythons internals. Heres some itneresting links: http://lambda-the-ultimate.org/node/1331 and http://www.rowehl.com/blog/?p=626