遞歸迭代返回等價嗎？

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