Recursive Functions, Stack Overflows, and Y-Combinators

Question

I have a recursive function (in C#) that I need to call about 800 million times; this would obviously normally result in a stack overflow after about the 900th call. I've kicked this out to multiple loops, but the recursive pattern is just so much easier, and cleaner to maintain.

I'm looking at implementing the recursive function using a y-combinator, as from what I'm reading and seen, that should solve the stack overflow problem, and fix the multiple nested loops.

Does anyone have experience using the y-combinator? Will I still be stuck in a stack overflow?

Take the simple example of a factorial. A factorial on most numbers bigger than like 5,000 will cause a stack overflow. If I used a y-combinator properly in that scenario, would it fix the stack overflow?

It doesn't seem trivial to implement, so I want to confirm it before I spend the development effort/resources implementing and learning the y-combinator.

Answer 1

No, using the Y-combinator will not help your situation. If you need to do something 800 million times, you can either (a) recurse, or (b) loop (or I suppose (c) write 800 million calls to your function). Since the Y-combinator doesn't loop, it must therefore recurse.

A loop is what you're looking for, unless you're using a runtime environment that offers proper tail recursion (such as Scheme).

Having said that, implementing the Y-combinator from scratch in the language of your choice is an excellent exercise.

Answer 2

Y combinators are useful but I think you really want tail recursion optimization that eliminates the use of the stack for tail recursive functions. Tail recursion is only possible when the result of every recursive call is immediately returned by the caller and never any additional computation after the call. Unfortunately C# does not support tail recursion optimization however you can emulate it with a trampoline which allows for a simple conversion from tail recursive method to a trampoline wrapped method.

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}

Answer 3

You can use trampoline as is used in Reactive Extension, I have tried to explain it on my blog http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

One solution is to convert your function(s) to use a loop and an explicit context data structure. The context represents what people generally think of as the call stack. You might find my answer to another question about converting to tail recursion useful. The relevant steps are 1 through 5; 6 and 7 are specific to that particular function, whereas yours sounds more complicated.

The "easy" alternative, though, is to add a depth counter to each of your functions; when it hits some limit (determined by experimentation), spawn a new thread to continue the recursion with a fresh stack. The old thread blocks waiting for the new thread to send it a result (or if you want to be fancy, a result or an exception to re-raise). The depth counter goes back to 0 for the new thread; when it hits the limit, create a third thread, and so on. If you cache threads to avoid paying the thread creation cost more often than necessary, hopefully you'll get acceptable performance without having to drastically restructure your program.