递归迭代返回等价吗？

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

我想将其转换为迭代形式，每次调用相当于推的东西明确的堆栈，但是每一个返回语句都会返回给调用者，这相当于什么？我想在每次调用后将位置保存在堆栈中，并在返回语句后再次返回，但这似乎是不可能的。

编辑：让自己更加明确，认为这更复杂随便举个例子：

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

Answer 2

如果你的函数是pure一个（即没有副作用），你可以使用memoization，或缓存。也就是说，将输入映射到输出，并在计算函数时首先使用它。

int randomNumber_with_memo(int n, std::map<int, int>& memo) 
{ 
    int& result = memo[n]; // find precalculated result; if not found, use 0 
    if (result == 0) // not found 
    { 
     int c1 = 1+randomNumber_with_memo(n-2, memo); 
     int c2 = 2 + randomNumber_with_memo(n-1, memo); 
     result = c1 + c2; // this also updates the memo 
    } 
    return result; 
} 

int randomNumber(int n) { 
    std::map<int, int> memo; 
    memo[-2] = 3; 
    memo[-1] = 3; 
    memo[0] = 3; 
    return randomNumber_with_memo(n, memo); 
} 

这主要是一劈：

• 它并不试图重复使用的randomNumber
• 不同调用之间的备忘录它采用了map代替更有效的vector（或阵列）
• 它依赖0作为标记值 - 它不应该是有效结果

但它有一个好处 - 你不必来分析你的代码。只需用memoization函数包装它，它可能会工作得更快。

注：这不会尝试递归转换为迭代。

Answer 3

时间最小化，你可以使用，因为许多插入的链接列表，而不是字符串：

#include <iostream> 
#include <list> 
#include <string> 
#include <utility> 

#include <iterator> 

using namespace std; 
int pal2(std::list<char>& s, decltype(declval<std::list<char>>().begin()) it , int i) 
{ 
    if (i > s.size()/2) { 
    return 0; 
    } 
    int c1, c2; 
    auto next = std::next (it ,1); 
    if(*it == *next) 
    { 
    s.insert(next, 'a'); 
    c1 = 1 + pal2(s,std::next (it ,1), i + 1); 
    s.erase(std::next (it ,1)); 
    } 
    else{ 
    c1 = pal2(s, std::next (it ,1), i + 1); 
    } 
    next = std::next (it ,2); 
    if (*it == *next) { 
    s.insert(next, 'b'); 
    c2 = 1 + pal2(s,std::next (it ,1), i + 1); 
    s.erase(std::next (it ,2)); 
    } 
    else { 
    c2 = pal2(s,std::next (it ,1), i + 1); 
    } 
    return c1 > c2 ? c1 : c2; 
} 
int main() 
{ 
    auto test = std::string("sssaaaasbbbabaaaaam"); 
    std::list<char> s(test.begin(),test.end()); 
    int i = 4; 
    std::cout << pal2(s, std::next(std::begin(s),i),i); 
}