部分尾遞歸函數是否仍然可以獲得完全尾遞歸函數的優化優勢？

我意識到這個問題的答案可能會因不同的語言而異，而我最感興趣的語言是C++。如果標籤需要更改，因爲這不能用與語言無關的方式回答，請隨時取消。部分尾遞歸函數是否仍然可以獲得完全尾遞歸函數的優化優勢？

是否有可能有一個函數是部分尾遞歸，並仍然有任何優勢，尾遞歸會得到你？

據我所知，尾遞歸不是完成一個完整的函數調用，編譯器會優化函數，只是將參數更改爲新參數並跳轉到函數的開頭。

如果你有這樣的功能：

def example(arg): 
    if arg == 0: 
     return 0 # base case 

    if arg % 2 == 0: 
     return example(arg - 1) # should be tail recursive 

    return 3 + example(arg - 1) # isn't tail recursive because 3 is added to the result

當優化器遇到類似的東西（其中函數是尾遞歸在某些情況下，而不是在其他人）將它打開一進一出jump而另一個變成call，或者將一些優化現實的事實（如果我知道它我不會問），它必須把所有變成call，並且失去了如果函數是尾隨函數時會產生的所有效率，遞歸？

來源

2011-08-23 Seth Carnegie

在流程，當我想到尾調用的，想到的第一語言，第二種情況是保證由語言規範尾調用。（術語注：最好是將此類函數調用爲「尾調用」。）

該計劃規範定義到底是什麼尾調用都在計劃和任務是編譯器支持他們特別。你可以在11.20中看到定義。尾部呼叫和尾部背景 R RS（source）。

請注意，在Scheme中，規範沒有說明優化尾部調用。相反，它表示實現必須支持無限數量的活動尾調用 - 語言運行時的語義屬性。它們可以作爲普通調用來實現，但通常不會。

例如，在C：

把你的例子的C版。

int example(int arg) 
{ 
    if (arg == 0) 
     return 0; 
    if ((arg % 2) == 0) 
     return example(arg - 1); 
    return 3 + example(arg - 1); 
}

使用gcc的常用優化設置（-O2）i386的編譯：

_example: 
    pushl %ebp 
    xorl %eax, %eax 
    movl %esp, %ebp 
    movl 8(%ebp), %edx 
    testl %edx, %edx 
    jne L5 
    jmp L15 
    .align 4,0x90 
L14: 
    decl %edx 
    testl %edx, %edx 
    je L7 
L5: 
    testb $1, %dl 
    je L14 
    decl %edx 
    addl $3, %eax 
    testl %edx, %edx 
    jne L5 
L7: 
    leave 
    ret 
L15: 
    leave 
    xorl %eax, %eax 
    ret

注意，有在彙編代碼中沒有函數調用。海灣合作委員會不僅將您的尾巴呼叫優化爲跳躍，還將非尾巴呼叫優化爲跳躍。

來源

2011-08-23 01:22:06

據我瞭解，一個聰明的編譯器可以通過只跳到例子切入點，而不是建立一個新的堆棧幀適用尾遞歸到你的第一個電話。下面的返回將把堆棧展開給原來的調用者，即使它不能爲另一個調用做到這一點，也能有效地「結束」兩個調用。

而你可以通過移動的3裏面調用的加入優化功能：

def example(arg, add=0): 
    arg += add 
    .... 
    return example(arg - 1, 3) # tail now too

另一種方法是創建第二個功能，同時具有相互調用。

我不知道是否Python或C++編譯器就可以搞定，雖然，但你可以檢查裝配輸出C++。奇怪的是我認爲檢查python的字節碼輸出可能會更困難。

來源

2011-08-23 01:06:55

是的，我知道我可以改變它在無條件尾部遞歸的地方，但我想舉一個我正在談論的例子。是的，我很確定C++（至少MSVC++）可以將相互遞歸函數轉換爲尾調用。 –

CPython實現*從不*優化尾部呼叫，而且Guido已將他的觀點放在了主題上，稱它爲「unpythonic」。見http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html –

@Dietrich是啊，我注意到這一點，當我試着本應該是一個尾遞歸析因函數:)太糟糕了guido是如此目光短淺。 –

部分尾遞歸函數是否仍然可以獲得完全尾遞歸函數的優化優勢？

回答

相關問題