c++ - 递归到迭代返回等效？

Question

假设这个随机代码看起来与我在这个问题中关注的工作技术相似:

int randomNumber(int n) {
    if (n <= 0)
        return 3;
    int c1 = 1+randomNumber(n-2);
    int c2 = 2 + randomNumber(n-1);
    return c1 + c2;
}

我想将它转换为迭代形式，每次调用都相当于将某些东西压入显式堆栈，但每条 return 语句都会将某些东西返回给它的调用者，它相当于什么？我想在每次调用后将位置保存在堆栈中，并在 return 语句后再次返回它，但这似乎是不可能的。

编辑:为了让自己更清楚，考虑这个更复杂的随机示例:

int pal(string s, int i) {
    if (i > s.length()/2) {
        return 0;
    }
    string s1 = s, s2 = s;
    int c1, c2;
    if (s1[i] == s1[i + 1]) {
        s1.insert(i + 1, "a");
        c1 = 1 + pal(s1, i + 1);
    }
    else {
        c1 = pal(s1, i + 1);
    }
    if (s2[i] == s2[i + 2]) {
        s2.insert(i + 2, "b");
        c2 = 1 + pal(s2, i + 1);
    }
    else {
        c2 = pal(s2, i + 1);
    }
    return c1 > c2 ? c1 : c2;
}

我不认为它会被同样简单地转换为迭代形式

EDIT2:我的问题最初是因为我想最小化这些函数的时间，例如我想最小化上一个例子的大字符串的时间(它几乎永远需要为程序计算大字符串的结果和上一个一样)

Answer 1

这几乎是斐波那契:

n = -1, r = 3
n = 0, r = 3
n = 1, r = 9 (1+3 + 2+3)
n = 2, r = 15 (1+3 + 2+9)
n = 3, r = 27 (1+9 + 2+15)
n = 4, r = 45 (1+15 + 2+27)
n = 5, r = 75 (1+27 + 2+45)
. . .

因此您可以使用简单的迭代算法来计算序列:

int randomNumer(int n)
{
    if (n <= 0)
        return 3;

    a = 3;
    b = 3;

    for (int i = 0; i < n; i++)
    {
        int t = a;
        a = b;
        b = (1 + t) + (2 + a);
    }

    return b;
}