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

Question

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

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

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

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

实现起来似乎并不简单，所以我想在投入开发工作/资源实现和学习 y 组合器之前确认一下。

Answer 1

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

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

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