如何将递归函数(有两个基本情况)转换为迭代函数？
如何将递归函数(有两个基本情况)转换为迭代函数？
提问于 2017-05-11 03:22:32
假设有以下递归函数：
int foo (int num)
{
if (num == 1)
return an int
else if (num == 2)
return another int
else
num foo(num-2) + foo(num-1)
}我的问题是：
1)如何将其他部分转换为其各自的迭代版本？我遇到过许多函数，其中一般情况是常数乘以(或添加)它的递归调用。尽管我以前从未遇到过这种情况。
else
return 3 * foo(n-1)( 2)你能给我一些关于如何将递归函数转换为迭代函数的技巧吗?特别是调用它自己的函数两次并计算它的和或乘法的函数(如上面的例子)？
非常感谢。
(编辑)
假设在调用此函数之前已经完成了错误检查。Num总是大于0或(0，∞)
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-05-11 03:38:37
1)
int foo (int num)
{
int foo1 = an int;
int foo2 = another int;
if (num < 2)
return foo1;
for (int n=2; n<num; ++n)
{
int foo3 = foo1+foo2;
foo1 = foo2;
foo2 = foo3;
}
return foo2;
}2)迭代实现通常需要对问题和解决方案有更深入的理解。在这种情况下，我发现计算foo(n)需要计算所有foo(1)...foo(n)，如果您还记得前两个步骤，那么每个步骤都可以完成。
Stack Overflow用户
发布于 2017-05-11 03:36:58
创建一个填充表A的函数，其中条目A[i]包含foo(i)的值。也就是说，将return替换为A[i] =，将对foo(i-1)的递归调用替换为查找A[i-1]。示例代码：
int foo (int num)
{
std::vector<int> results(num+1);
for (int i = 1; i <= num; ++i) {
if (i == 1)
results[i] = an int
else if (i == 2)
results[i] = another int
else
results[i] = results[i-2] + results[i-1]
}
return results[num];
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43905987
复制相关文章
相似问题
腾讯云开发者
