递归函数、堆栈溢出和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

你可以使用响应式扩展中使用的trampoline，我已经尝试在我的博客http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/上解释过了