這個遞歸函數是如何自動轉換爲迭代函數的？

尾遞歸是指在最後一行遞歸調用。尾遞歸可以通過封閉 while循環和替換遞歸調用與每函數參數的一個分配機構消除。

例如

void print(Iterator start, Iterator end, ostream& out=cout) { 
    if(start == end) 
     return; 
    out << *start++ << endl; 
    print(start, end, out); 
}

轉換爲迭代由上述說明書作爲

void print(Iterator start, Iterator end, ostream& out=cout) { 
    while(true) { 
     if(start == end) 
      return; 
     out << *start++ << endl; 
    } 
}

在上述通道中提到，「每函數參數一個分配代替遞歸調用，但在給定的例子中，我們沒有任何任務？

任何人都可以解釋並舉例說明如何將遞歸轉換爲迭代函數的上述解釋？

來源

2011-08-29 venkysmarty

我認爲他們的表達不準確，他們的真正含義是你可以每個循環做一次操作，而不是每次函數調用一次。在這種情況下，輸出語句（'out <<'） – mydogisbox

遞歸迭代應該是這樣的總體轉化率。

原始代碼：

void print(Iterator start, Iterator end, ostream& out=cout) { 
    if(start == end) 
     return; 
    out << *start++ << endl; 
    print(start, end, out); 
}

轉換的代碼：

void print(Iterator start, Iterator end, ostream& out=cout) { 
    while(true) { 
    if(start == end) 
     return; 
    out << *start << endl; 

    // One assignment per function argument for 'general' tail recursion 
    start = start + 1;  // (1) 
    end = end;    // (2) 
    out = out;    // (3) 
    } 
}

三個分配如在解釋也包括在內。賦值（1）嵌入在start++中，賦值（2）和（3）被優化掉。

來源

2011-08-29 13:09:14 vsekhar

好吧，如果你想對轉換非常嚴格，第二個代碼應該在輸出表達式中增加'start'（與第一個代碼類似），並且只需在循環結尾執行'start = start' 。這就是爲什麼這個例子被嚴重挑選的原因，它不會在遞歸調用中傳遞參數時修改參數。 –

分配隱藏在遞增運算符：

start++;

實際上是一個任務：

start = start+1;

實際上，例如（第一部分）不是很好。

out << *start++ << endl; 
print(start, end, out);

應該

out << *start << endl; 
print(start+1, end, out);

來源

2011-08-29 12:59:51

不正確。這兩項任務都在這兩個例子中。 – mydogisbox

@mydogisbox：我編輯了我的答案以顯示「典型」遞歸調用。 –

不錯的說明 - 最初的例子用一個完全相同的賦值「替換」一個賦值非常混亂。 – molbdnilo

它隱藏在C++一點，但start++被分配一個新的值在每次循環的時間。

來源

2011-08-29 13:01:47

不正確。這兩項任務都在這兩個例子中。 – mydogisbox

我不認爲，你所指的任何段落都很重要;只專注於主要的問題，要一個遞歸函數轉換爲正常的迭代函數，這是可以做到（輕鬆）的，

void print(Iterator start, Iterator end, ostream& out=cout) { 
    while(start != end) { 
     out << *start++ << endl; 
    } 
}

來源

2011-08-29 13:03:08 iammilind

+1。正確和簡潔。 :-) – Nawaz

他們在說的是，您將tail函數調用的參數賦值給此函數調用的參數變量，但在這種情況下，它不是必需的，因爲您使用完全相同的參數調用該函數（因爲像其他人所說的那樣，在函數調用之前發生了對第一個參數start的更改）。

實際上，如果做確切的說，迭代函數應該像

void print(Iterator start, Iterator end, ostream& out=cout) { 
    while(true) { 
     if(start == end) 
      return; 
     out << *start++ << endl; 

     start = start; 
     end = end; 
     out = out; 
    } 
}

但這些作業是完全不必要的，即使conpectually正確。

來源

2011-08-29 13:12:02

這個遞歸函數是如何自動轉換爲迭代函數的？

回答

相關問題