c++ - 如何将递归函数(有两个基本情况)转换为迭代函数？

Question

假设有以下递归函数:

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 部分转换为其各自的迭代版本？我遇到过很多函数，其中一般情况是一个常数乘以(或加)它的递归调用。虽然我以前没有遇到过这种情况。

else
    return 3 * foo(n-1)

2) 你能给我一些关于如何将递归函数转换为迭代函数的技巧吗，尤其是调用它自己的函数两次并计算它的和或乘法的函数(就像上面的例子)？

非常感谢。

(编辑)

假设在调用此函数之前已完成错误检查。 Num总是大于0或(0,∞)

Answer 1

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)，并且如果您还记得前两个，则每一个都可以一步完成。