Geek Answers Handbook

Recursive functions, stack overflow and Y-combinators

I have a recursive function (in C #) that I need to call about 800 million times; this obviously leads to a stack overflow after the 900th call. I threw it out for several cycles, but the recursive pattern is much simpler and more convenient to maintain.

I am looking for an implementation of a recursive function using y-combinator, since from what I read and see, this should solve the problem and fix multiple nested loops.

Does anyone have any experience using y-combinator? Will I still depend on?

Take a simple factorial example. Factor for most numbers greater than 5000 will lead to a stack overflow. If I used y-combinator correctly in this scenario, would I fix the stack overflow?

This does not seem trivial to implement, so I want to confirm it before spending resources / resources for developing and training y-combinator.

+5
source share
4 answers

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

A loop is what you are looking for, unless you use a runtime that offers the right tail recursion (like a circuit).

, Y-combinator - .

+6

Y , , , . , . , # , , .

// 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);
}
+6

. , . . - 1 5; 6 7 , .

"" ; ( ), , . ( , ). 0 ; , . , , , , .

+1

More articles:


All Articles