如何識別什麼是，什麼不是尾遞歸？

有時它很簡單（如果自我調用是最後一個語句，它是尾遞歸），但仍有一些情況令我困惑。一位教授告訴我，「如果在自助之後沒有執行的指令，那就是尾遞歸」。這些例子如何（忽略它們沒有多大意義的事實）：如何識別什麼是，什麼不是尾遞歸？

a）這一個應該是尾遞歸的，看看自我調用是最後一個語句，並且在它之後沒有什麼可以執行的。

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else 
     return foo(n-2); 
}

b）但是這個怎麼樣？它應該是一個尾部調用，因爲如果條件爲真，除了它將被執行，但它不是最後一個語句？

function foo(n) 
{ 
    if(n != 0) 
     return foo(n-2); 
    else 
     return 0; 
}

c）這個怎麼樣？在這兩種情況下，自我呼叫將是最後執行的事情：

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else  
    { 
     if(n > 100) 
      return foo(n - 2); 
     else 
      return foo(n - 1); 
    } 
}

來源

2010-09-09 fingerprint211b

它可能會幫助你考慮如何實際實現tail-call優化。當然，這不是定義的一部分，但它確實激發了定義。

通常情況下，當一個函數被調用時，調用代碼將在堆棧中存儲稍後需要的任何寄存器值。它還會存儲一個返回地址，表示通話後的下一條指令。它將執行所需的任何操作來確保爲被調用者正確設置堆棧指針。然後它將跳轉到目標地址[*]（在這種情況下，相同的功能）。返回時，它知道返回值位於由調用約定（寄存器或堆棧槽）指定的位置。

對於尾部呼叫，呼叫者不會這樣做。它忽略了任何寄存器值，因爲它知道以後不需要它們。它設置堆棧指針，以便被調用者使用與調用者所用的堆棧相同的堆棧，並且不會將自身設置爲返回地址，而只是跳轉到目標地址。因此，被調用者將覆蓋相同的堆棧區域，它將把它的返回值放在調用者放置其返回值的相同位置，並且當它返回時，它不會返回給它的調用者，而是返回到其調用者的呼叫者。

因此，非正式地，當可能發生尾部呼叫優化並且尾部呼叫的目標是功能本身時，函數是尾遞歸的。該效果或多或少與該函數包含循環相同，而不是自行調用，尾部調用跳轉到循環的開始處。這意味着在調用之後必須沒有需要的變量（並且實際上沒有「工作要做」，這在C++語言中意味着什麼都不會被破壞），並且調用者必須返回尾部調用的返回值。

這是所有的簡單/平凡的尾遞歸。有些轉換可以用來做一些還沒有的尾遞歸，例如引入額外的參數，存儲「最底層」遞歸級別所使用的一些信息，做一些本來可以完成的工作出路」。因此，例如：

int triangle(int n) { 
    if (n == 0) return 0; 
    return n + triangle(n-1); 
}

可製成尾遞歸，要麼由程序員或一個足夠聰明的編譯器自動，就像這樣：

int triangle(int n, int accumulator = 0) { 
    if (n == 0) return accumulator; 
    return triangle(n-1, accumulator + n); 
}

因此，前者的功能可以被描述爲「尾巴遞歸「的人正在談論一個足夠聰明的語言/編譯器。準備好這一變體使用。存儲返回地址，移動堆棧指針和跳轉，可能會或不可能被體系結構封裝在單個操作碼中，但即使不是這通常會發生什麼情況。

來源

2010-09-09 18:22:32

是的;我認爲你的教授意味着在任何路徑上，如果最終指令是遞歸的，那麼它是尾遞歸。

所以，這三個例子都是尾遞歸的。

來源

2010-09-09 16:36:30 Vermiscious

所有的函數都是尾遞歸的。

沒有指令後留下的自呼

是指：自呼後，您從功能返回，即沒有更多的代碼已被執行，而不是有函數中沒有更多的代碼行。

來源

2010-09-09 16:36:49 Dario

這三個例子都是尾遞歸的。一般來說，如果函數的結果（「return」關鍵字後面的表達式）是對函數本身的單獨調用，則它是尾遞歸。 沒有其他操作員必須參與表達式的最外層。如果對自身的調用只是表達式的一部分，那麼機器必須執行調用，但必須返回到對所述表達式的評估中，也就是說，它不在函數執行的尾部，而是在一種表達。然而，這不適用於遞歸調用可能採用的任何參數：在那裏允許任何事物，包括對其自身的遞歸調用（例如「return foo（foo（0））;」）。當然，優化跳轉調用僅適用於外部調用。

來源

2010-09-09 16:52:21 slartibartfast

如何識別什麼是，什麼不是尾遞歸？

回答

相關問題