5

我有一个递归函数（在 C# 中），我需要调用大约 8 亿次；这显然通常会在第 900 次调用后导致堆栈溢出。我已经将它踢出多个循环，但递归模式更容易维护，也更清洁。

我正在考虑使用 y-combinator 实现递归函数，正如我正在阅读和看到的那样，这应该可以解决堆栈溢出问题，并修复多个嵌套循环。

有人有使用 y-combinator 的经验吗？我还会被困在堆栈溢出中吗？

以阶乘的简单示例为例。大多数大于 5,000 的数字的阶乘将导致堆栈溢出。如果我在那种情况下正确使用了 y 组合器，它会修复堆栈溢出吗？

实施起来似乎并不简单，所以我想在我花费开发工作/资源实施和学习 y-combinator 之前确认它。

4

4 回答 4

6

不，使用 Y 组合器对您的情况没有帮助。如果您需要执行 8 亿次操作，您可以 (a) 递归或 (b) 循环（或者我想 (c) 为您的函数编写 8 亿次调用）。由于 Y 组合器不循环，因此它必须递归。

除非您使用提供适当尾递归的运行时环境（例如 Scheme），否则您正在寻找循环。

话虽如此，以您选择的语言从头开始实现 Y-combinator 是一个很好的练习。

于 2011-12-02T07:14:14.170 回答
6

Y 组合器很有用，但我认为您确实需要尾递归优化，以消除尾递归函数的堆栈使用。尾递归只有在每次递归调用的结果都由调用者立即返回并且在调用之后不再进行任何额外计算时才可能。不幸的是，C# 不支持尾递归优化，但是您可以使用蹦床来模拟它，它允许从尾递归方法到蹦床包装方法的简单转换。

// 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);
}
于 2011-12-02T07:42:10.907 回答
5

您可以使用在 Reactive Extension 中使用的 trampoline，我已尝试在我的博客http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/上对其进行解释

于 2011-12-02T08:36:10.900 回答
1

一种解决方案是将您的函数转换为使用循环和显式上下文数据结构。上下文代表人们通常认为的调用堆栈。您可能会发现我对另一个关于转换为尾递归的问题的回答很有用。相关步骤为 1 到 5；6 和 7 是特定于该特定功能的，而您的听起来更复杂。

但是，“简单”的替代方法是为您的每个功能添加一个深度计数器；当它达到某个限制（由实验确定）时，生成一个新线程以使用新堆栈继续递归。旧线程阻塞等待新线程向其发送结果（或者，如果您想花哨的话，可以重新引发结果或异常）。新线程的深度计数器返回 0；当它达到限制时，创建第三个线程，依此类推。如果您缓存线程以避免不必要地支付线程创建成本，那么您将获得可接受的性能，而无需大幅重组程序。

于 2011-12-02T11:07:01.340 回答