尾遞歸究竟是好是壞？
最近在看《數據結構與演算法分析，c語言描述》，這裡提到了尾遞歸的概念，書中說尾遞歸是遞歸的一種不好的應用，但是在網上查了一下，看到的對於尾遞歸的描述都是說他的效率比一般遞歸高，且不會造成堆棧溢出，和書中的描述有很大區別啊。求大神可以為我解答一下。書中提到的tail recursion就是圖3.54的代碼。
有尾遞歸優化才比普通遞歸好，而且要注意是「比普通遞歸好」，不是比任意實現都好。這種代碼一般都非常容易寫成循環，沒有必要讓編譯器去優化吧。
遞歸是一種很好的編程思想：簡潔、直觀，令人一目了然；缺點是必須事先確定棧不會溢出、函數調用/返回比循環要慢（需要額外考慮參數傳遞、保護執行現場、局部變數的維護等：所有這些都可能要佔用棧空間，這就使得遞歸層數一旦超過預期就很容易造成stackoverflow）。
已經證明，所有的遞歸都可以改成遞推（但往往需要自己維護一個棧）；尤其是其中的尾遞歸，甚至可以按一些機械的步驟改寫成循環，並不需要棧的幫助。
相比尾遞歸，循環佔用的內存空間小而確定，並且無需傳遞參數、保護執行現場、局部變數只需分配一次：可見，無論在時間還是空間上，循環的消耗都比尾遞歸小得多（空間可能僅有尾遞歸的1/N，對簡單遞歸，時間可能也接近1/N。N是實際遞歸次數）。
很明顯，我們就應該用循環替換掉所有的尾遞歸——但前面提到過，尾遞歸甚至可以「通過一些機械的步驟」改寫成循環：這「機械的步驟」，不應該是機器的事嗎？所以，現在幾乎所有編譯器都有「尾遞歸優化」能力。
如果確定自己的編譯器有這種能力，某些問題可能還是直接寫尾遞歸更好：代碼是遞歸，簡潔直觀，編寫、閱讀、維護都更方便；而編譯後的機器碼則是循環，小而快又不會溢出，可謂兩全其美。我個人感覺，雖然從定義問題的角度來看，尾遞歸是更直觀的，但從解決問題的角度來看，卻是循環更直觀。所以我在絕大多數情況下都會寫循環。
在極端情況下，尾遞歸解法會比循環更直觀。這種極端情況我可能經歷過1次，但不記得了。圖片上劃線的後面一句給出來在這本書中尾遞歸的定義：tail recursion refers to a recursive call at the last line.
at the last line在這裡可以理解為在函數return前的一個語句。
所以在這本書中尾遞歸的定義是：函數結束前的遞歸調用。
現在再來分析，這裡說尾遞歸不好，是因為在這個遞歸調用結束以後函數也隨之結束，並且用不到函數的返回值（因為函數返回值void，沒有返回值）。這個時候，完全可以用一個循環來代替遞歸調用，也就是用循環結構代替尾遞歸。
舉一個快排的例子，這裡對指針s和e之間的int類型元素排序：
void sort(int *s, int *e){ if(s &< e) { int *p= partition(s, e); sort(s, p - 1); //標號1 sort(p + 1, e); // 標號2 }}
標號2處就是一個尾遞歸。這個快排函數完全可以改成：
void sort(int *s, int *e){ while(s &< e) { int *p = partition(s, e); sort(s, p - 1); //標號1 s = p + 1; //標號2 }}
這樣就減少了一次遞歸調用，當然這只是表面的，在標號1當中仍然會有這樣的優化，減少的遞歸調用次數就更多了。
這樣看來，既然尾遞歸可以優化，自然是能優化就優化了。
一點題外話：如果按照「tail recursion refers to a recursive call at last line.」的定義，在要返回尾遞歸的值時，這時尾遞歸就有可能是不可避免的了。比如一個函數 f：
datatype f(...)
{ ... datatype a = f(...); return a;}按照定義，datatype 那一行就可以叫做一個尾遞歸。但因為要返回值，這就不大可能避免。當然有一點編程基礎的人都會把最後兩句合併成: return f(...);這個遞歸無法避免，但合併以後，按照定義就不是一個尾遞歸了。
以上。。。（因為最近在山裡，手機純手打，代碼格式之類的請見諒了）所謂效率比一般遞歸高且不會溢出，是因為編譯器替你把尾遞歸改成了循環，並沒有傻傻真做遞歸。你可以選擇做傻碼農，把活兒留給編譯器，也可以自己直接寫循環版。這一點Weiss也寫了吧～
Python 之父 Guido van Rossum 好像曾說過不要用尾遞歸，循環比尾遞歸更自然。一開始我不以為然，因為那時我對尾遞歸的印象就是求最大公約數的遞歸演算法，以及題圖的例子，覺得還是簡潔明快的。
在粗淺地接觸了函數式後，我發現，若想使用純函數式的方式、無副作用地實現某些迭代操作，就會陷入高開銷的非尾遞歸和不自然的尾遞歸之間的兩難選擇（不考慮語言庫封裝好的迭代用輪子。）。以對一個 List[Int] 求和為例：
def sum1(xs: List[Int]): Int = {
if (xs.isEmpty) 0
else xs.head + sum1(xs.tail)
}
def sum2(xs: List[Int]): Int = {
def loop(curr: List[Int], acc: Int): Int = {
if (curr.isEmpty) acc
else loop(curr.tail, acc + curr.head)
}
loop(xs, 0)
}
你寫個簡單的尾遞歸，然後gcc編譯成彙編，你再看看
估計你會發現你的遞歸調用不見了
編譯器：做了點微小的工作，謝謝大家尾遞歸當然好了。。。。尾遞歸基本等於循環啊。。。但是既然尾遞歸了為啥不直接寫出循環，並不是所有編譯器都會對尾遞歸做清棧優化的吧
作為不用寫編譯器的我來說，知道我常用的lua c++ 都支持尾遞歸優化就夠了。至於偶爾用的java python oc，反正偶爾用已經說明情況了，不差那點效率。知道自己常用語言是否支持某個特性就夠了，知道原理不一定是必須的
反正能用循環的，不要用遞歸
推薦閱讀：
※Google MapReduce中的map和reduce與函數式編程中的map，reduce有何異同？
※GitHub 上出眾的程序員有哪些？
※non-trivial 怎樣翻譯?
※如何優雅地將程序設計語言的名字翻譯成漢語？
※大牛編程用的是什麼系統？什麼語言？什麼編譯器？