0

知道每个递归函数都可以转换为迭代版本。有人可以帮我找到这个伪代码的迭代版本吗？我正在尝试优化代码，递归显然不是要走的路

sub calc (a, b )
{
    total = 0;
    if(b <= 1) 
        return 1
    if( 2*a > CONST)
        for i IN (1..CONST)
            total += calc(i, b-1) ;
    else
        for j IN (2*a..CONST)
            total += calc(j, b-1) ;
    return total;
}
CONST = 100;
print calc (CONST,2000);

谢谢您的帮助！

4

2 回答 2

2

从递归到迭代的重构并不是解决您的性能问题的答案。该算法从缓存中获益最多，与斐波那契数列的方式大致相同。

在 F# 中编写了一个简短的测试程序后，带有一些示例数据（CONST = 5, a = 0..10, b = 2..10）：

  • 原程序耗时 6.931 秒
  • 缓存版本耗时 0.049 秒

解决方案是保留一个带有键的字典tuple(a,b)并在计算之前查找值。这是带有缓存的算法：

dictionary = new Dictionary<tuple(int, int), int>();

sub calc (a, b )
{
    if (dictionary.Contains(tuple(a,b)))
        return dictionary[tuple(a,b)];
    else
    {
        total = 0;
        if(b <= 1) 
            return 1
        if( 2*a > CONST)
            for i IN (1..CONST)
                total += calc(i, b-1);
        else
            for j IN (2*a..CONST)
                total += calc(j, b-1);

        dictionary[tuple(a,b)] = total;
        return total;
    }
}

编辑：只是为了确认不是我的测试的迭代性质导致了性能提升，我用一组参数（CONST = 5, a = 6, b = 20）再次尝试了它们。

  • 缓存版本耗时 0.034 秒
  • 原始版本仍在运行...（2 分钟以上）
于 2013-04-12T15:48:08.223 回答
0

只有尾递归算法可以转换为迭代算法。您提供的代码绝对不是尾递归的，因此它不能轻易转换为迭代形式。

性能问题的解决方案是记忆化

于 2013-04-13T01:16:00.197 回答