递归函数,堆栈溢出和Y组合器

Question

我有一个递归函数(在C#中),我需要调用大约8亿次; 这显然通常会在大约第900次呼叫后导致堆栈溢出.我已经将它踢出了多个循环,但递归模式更容易,维护更清晰.

我正在考虑使用y-combinator实现递归函数,就像我正在阅读和看到的那样,它应该解决堆栈溢出问题,并修复多个嵌套循环.

有没有人有使用y-combinator的经验？我还会陷入堆栈溢出吗？

以一个阶乘的简单例子为例.大多数数字大于5,000的因子将导致堆栈溢出.如果我在那个场景中正确使用了y-combinator,它会修复堆栈溢出吗？

它实现起来似乎微不足道,所以我想在开发工作/资源实现和学习y-combinator之前确认它.

Answer 1

不,使用Y-combinator无助于您的情况.如果你需要做8亿次,你可以(a)递归,或(b)循环(或者我认为(c)写入你的函数8亿次).由于Y-combinator不循环,因此必须递归.

除非您使用提供正确尾递归的运行时环境(例如Scheme),否则循环就是您正在寻找的循环.

话虽如此,用你选择的语言从头开始实现Y-combinator是一个很好的练习.

Answer 2

Y组合器很有用,但我认为你真的想要尾递归优化,它不需要使用堆栈来实现尾递归函数.尾递归只有在调用者立即返回每个递归调用的结果时才有可能,并且在调用之后永远不会有任何额外的计算.不幸的是,C#不支持尾递归优化,但你可以使用trampoline来模拟它,这允许从尾递归方法到trampoline包装方法的简单转换.

// 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

您可以像在Reactive Extension中使用的那样使用蹦床,我试图在我的博客上解释它http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/