递归到迭代转换

了解每个递归函数都可以转换为迭代版本。有人可以帮我找到这个伪代码的迭代版本吗？我试图优化代码和递归显然不是要走的路线递归到迭代转换

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);

感谢您的帮助！

来源

2013-04-12 Techmonk

什么是总数？它是在别处定义还是应该在函数体内初始化？ – AlexFoxGill

在体内初始化 – Techmonk

谢谢。另外，也许你可以提供一些样本输入和输出？算法看起来几乎就像你不需要迭代或递归，而只是一个数学公式。 – AlexFoxGill

从递归到迭代的重构不是解决您在这里的性能问题的答案。该算法从高速缓存中获益最多，与Fibonacci序列的方法大致相同。

在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-12 15:48:08 AlexFoxGill

好主意，但我认为它需要一些改进，因为我们从来没有为相同的a调用函数，b对缓存不会以这种方式帮助很多。 – Techmonk

@Techmonk实际上，您可以调用相同的a，b对的函数。 – JakeP

你是对的！去实现内存 – Techmonk

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

解决您的性能问题是Memoization

来源

2013-04-13 01:16:00 GoZoner

递归到迭代转换

回答

相关问题