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

Question

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

我正在考虑使用 y 组合器实现递归函数，从我正在阅读和看到的内容来看，这应该可以解决堆栈溢出问题，并修复多个嵌套循环。

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

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

实现起来似乎并不简单，所以我想在花费开发精力/资源来实现和学习 y-combinator 之前确认一下。

Answer 1

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

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

话虽如此，用您选择的语言从头开始实现 Y 组合器是一个很好的练习。

Answer 2

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

Answer 3

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

Answer 4

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

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