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);
}