尾遞歸函數總是要避免？

如果我記得正確，尾遞歸函數總是有一個簡單的非遞歸等價。由於遞歸涉及不必要的函數調用開銷，所以最好不要使用非遞歸方式。尾遞歸函數總是要避免？

這個假設總是如此嗎？是否有任何其他論點/反對尾遞歸？

2010-07-20 AbdullahC

如果您使用的編譯器語言優秀，那麼可以優化這些類型的遞歸，所以在這些情況下，如果它提高了使用遞歸的可讀性，我會說堅持下去。

2010-07-20 11:34:51

聽起來不錯，但現在歡迎來到現實世界。你寫一個遞歸函數而不是迭代函數。編譯器不會將其轉換爲迭代的。它會一直工作，直到您遇到足夠長的輸入。你的同事過來解釋你是多麼的錯誤。你重寫它。 – sharptooth 2010-07-20 11:42:30

這實際上取決於你對環境的瞭解以及函數在迭代形式中的邪惡/無邪。當然是務實的。我認爲，尾遞歸函數並不總是可以避免的。 – 2010-07-20 11:53:14

謝謝，fd。你和其他答覆者已經解釋了爲什麼使用尾遞歸有時是有意義的。 – AbdullahC 2010-07-20 12:21:46

這取決於語言，但往往開銷並不大。這可能是主觀的，但遞歸函數往往更易於理解。大多數情況下，您不會注意到性能差異。

我會去尋找尾遞歸，除非我的平臺在處理它時非常糟糕（即根本沒有這樣做，但總是推入棧中）。

來源

2010-07-20 11:34:19

不，這並非總是如此。許多語言和/或編譯器可以輕鬆地優化尾遞歸調用，並將其重寫爲迭代版本，或以某種方式重用堆棧幀以用於後續調用。

Scheme語言任務，落實使用tail call optimization

GCC可以優化尾調用爲好，考慮在一個鏈表釋放所有節點的功能：

void free_all(struct node *n) 
{ 
    if(n != NULL) { 
     struct node *next = n->next; 
     free(n); 
     free_all(next); 
    } 
}

編譯成，與優化：

free_all: 
     pushl %ebp 
     movl %esp, %ebp 
     pushl %ebx 
     subl $20, %esp 
     movl 8(%ebp), %eax 
     testl %eax, %eax 
     je  .L4 
     .p2align 4,,7 
     .p2align 3 
.L5: 
     movl 4(%eax), %ebx 
     movl %eax, (%esp) 
     call free 
     testl %ebx, %ebx 
     movl %ebx, %eax 
     jne  .L5 
.L4: 
     addl $20, %esp 
     popl %ebx 
     popl %ebp 
     ret

也就是說，一個簡單的跳躍，而不是recursivly調用free_all

來源

2010-07-20 11:36:03 nos

Upvoted爲實際示例。 – jrockway 2010-10-06 21:41:21

第

爲了便於閱讀，許多計算可以更好地表達爲遞歸（尾部或其他）函數。如果你的編譯器沒有進行尾部調用優化，並且你希望你可能吹掉調用堆棧，唯一的原因是避免它們。

來源

2010-07-20 11:37:28

尾遞歸函數總是要避免？

回答

相關問題