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

Question

我有一个递归函数（在C＃中），我需要调用约8亿次；显然，这通常会导致在第900次调用后出现堆栈溢出。我已经将其踢出了多个循环，但是递归模式非常容易，而且维护起来也更简洁。

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

有人有使用y组合器的经验吗？我还会被卡在堆栈溢出中吗？

以阶乘的简单示例为例。大多数大于5,000的数字的阶乘将导致堆栈溢出。如果在那种情况下正确使用y-combinator，它将解决堆栈溢出问题吗？

实现起来似乎并不容易，所以我想在花费开发工作/资源实现和学习y-combinator之前先进行确认。

Answer 1

否，使用Y组合器不会帮助您解决问题。如果您需要执行8亿次操作，则可以（a）递归，或（b）循环（或者我想（c）向函数编写8亿次调用）。由于Y组合器不会循环，因此必须递归。

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

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

Answer 2

Y组合器很有用，但我认为您真的想要尾部递归优化，该优化消除了对尾部递归函数使用堆栈。尾递归仅在调用者立即返回每个递归调用的结果并且在调用之后不再进行任何其他计算时才可行。不幸的是，C＃不支持尾递归优化，但是您可以用蹦床对其进行仿真，它允许从尾递归方法简单地转换为蹦床包裹的方法。 通用标签

Answer 3

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

Answer 4

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

不过，“简便”的替代方案是为每个函数添加一个深度计数器。当达到某个限制（由实验确定）时，生成一个新线程以使用新堆栈继续递归。旧线程阻塞等待新线程将结果发送给它（或者，如果您想获得结果，或者重新引发异常）。对于新线程，深度计数器将返回0；否则，深度计数器将返回0。当达到极限时，创建第三个线程，依此类推。如果您缓存线程以避免多于必要地支付线程创建成本，则希望您能够获得可接受的性能，而不必彻底地重组程序。