递归函数，堆栈溢出和Y-Combinators

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

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

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

举一个简单的因子例子。对大于5000的大多数数字进行阶乘会导致堆栈溢出。如果我在这种情况下正确使用了y-combinator，它会修复堆栈溢出吗？

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

来源

2011-12-02 Brian Deragon

不，使用Y-combinator不会帮助你的情况。如果你需要做8亿次，你可以（a）递归，或者（b）循环（或者我认为（c）向你的函数写入8亿次调用）。由于Y组合器不循环，因此它必须递归。

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

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

来源

2011-12-02 07:14:14

不幸的是，不，我正在使用C＃，并且跨越3个独立的集合进行循环，每个集合生成2到3个内部集合，需要调用多达8个不同版本的同一个函数，在他们之间变化。我设法将它重写为一个函数（仍然接近120行），它会递归地调用它自己，但不会使用尾递归，因此它会在第900次调用时爆炸。 –

据我了解，C＃支持.NET 4.0以来的适当尾递归：[.NET Framework 4中的尾调用改进]（http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail -call-improvements-in-net-framework-4.aspx）和[C＃和F＃中的尾递归]（http://lookingsharp.wordpress.com/2010/03/08/tail-recursion-in-csharp-and -fsharp /）。当编译任何CPU并在64位机器上运行程序时，它肯定会进行尾递归优化 - 如果这有帮助... –

@SaschaHennig：很高兴知道，谢谢。 –

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-02 07:42:10

您可以使用蹦床作为无扩展时，我试图解释它在我的博客http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

来源

2011-12-02 08:36:10

一种解决方案是将您的功能（S）使用循环和明确上下文数据结构。上下文表示人们通常认为的调用堆栈。你可能会发现my answer to another question about converting to tail recursion有用。相关步骤是1到5; 6和7对特定功能是特定的，而你的听起来更复杂。

然而，“简单”的选择是为每个函数添加深度计数器;当它遇到一些限制（由实验确定）时，产生一个新的线程以继续递归，使用新的堆栈。旧线程阻塞等待新线程发送一个结果（或者如果你想要看，结果或重新提升的例外）。新线程的深度计数器回到0;当它达到极限时，创建第三个线程，依此类推。如果您缓存线程以避免更频繁地支付线程创建成本，希望您可以获得可接受的性能，而无需彻底重组您的程序。

来源

2011-12-02 11:07:01

递归函数，堆栈溢出和Y-Combinators

回答

相关问题