2

是否存在具有最高效率输出和尾递归的迭代递归或反之亦然算法？

首选的语言是 C#。

例如：在输入这​​个算法得到下一个简单的函数：

public static ulong Factorial(ulong n)
{
    return n == 0 ? 1 : n * Factorial(n - 1);
}

并在处理返回后：

public static ulong Factorial(ulong n)
{
    ulong result = 1;
    for (ulong i = 1; i <= n; i++)
        result = result * i;
    return result;
}
4

3 回答 3

2

是的，总是可以从递归算法创建迭代版本。我不知道 C# 是否存在用于执行此操作的程序/代码重写器。这种技术已经得到了很好的研究，您可以找到一般参考资料，例如从递归到迭代：优化是什么？（pdf文件）。
最坏的情况是简单地“模拟”堆上的堆栈以保存函数的状态以供将来使用。最简单的情况可能是尾递归循环。有很多关于这个主题的文章。
另一方面，从通用迭代算法创建递归版本的研究较少，但它确实存在，

于 2012-09-16T19:11:53.007 回答
0

我唯一知道的是，递归可以同样转换为非递归stack，因为它实际上是这样做的，你可以自己做。

顺便说一句，您可能会想到某些无法转换为简单迭代的情况。

于 2012-09-16T19:12:56.563 回答
0

我不知道进行这种转换的算法的简单通用实现，但是使用非常通用的动态编程方法优化递归算法是微不足道的。

例如，如果您将每个调用的结果缓存Factorial在字典中（来自n->的映射Factorial(n)），您将获得等于迭代的算法复杂度（但！只有时间复杂度。此方法使用更多内存） . 请注意，简单地“模仿”您自己的堆栈在算法复杂性方面并没有给您带来任何好处。

缓存非常容易实现和应用，适用于广泛的算法。

Wikipedia 页面上有关于您的示例算法的特定条目。

于 2012-09-16T19:23:05.117 回答