本文摘抄自什么是尾遞歸
問題一：什么是尾遞歸?
這兩個(gè)函數(shù)都是在計(jì)算n的階乘惭蹂，結(jié)果一樣的，但只有下面的facttail函數(shù)才是尾遞歸。所以可以看出烧栋，尾遞歸的概念就是函數(shù)返回之前的最后一個(gè)操作若是遞歸調(diào)用，則該函數(shù)進(jìn)行了尾遞歸拳球，而上面的fact函數(shù)审姓，最后一個(gè)操作是乘法，所以顯然不是尾遞歸祝峻。
問題二：尾遞歸優(yōu)化的原理是什么魔吐？
我們知道遞歸調(diào)用是通過棧來實(shí)現(xiàn)的扎筒，每調(diào)用一次函數(shù)，系統(tǒng)都將函數(shù)當(dāng)前的變量酬姆、返回地址等信息保存為一個(gè)棧幀壓入到棧中嗜桌，那么一旦要處理的運(yùn)算很大或者數(shù)據(jù)很多，有可能會(huì)導(dǎo)致很多函數(shù)調(diào)用或者很大的棧幀辞色，這樣不斷的壓棧骨宠，很容易導(dǎo)致棧的溢出。我們回過頭看一下尾遞歸的特性相满，函數(shù)在遞歸調(diào)用之前已經(jīng)把所有的計(jì)算任務(wù)已經(jīng)完畢了层亿，他只要把得到的結(jié)果全交給子函數(shù)就可以了，無需保存什么立美，子函數(shù)其實(shí)可以不需要再去創(chuàng)建一個(gè)棧幀匿又，直接把就著當(dāng)前棧幀，把原先的數(shù)據(jù)覆蓋即可建蹄。相對的琳省，如果是普通的遞歸，函數(shù)在遞歸調(diào)用之前并沒有完成全部計(jì)算躲撰，還需要調(diào)用遞歸函數(shù)完成后才能完成運(yùn)算任務(wù)针贬，比如return n * fact(n - 1);這句話，這個(gè)fact(n)在算完fact（n-1）之后才能得到n * fact(n - 1)的運(yùn)算結(jié)果然后才能返回拢蛋。綜上所述桦他，編譯器對尾遞歸的優(yōu)化實(shí)際上就是當(dāng)他發(fā)現(xiàn)你丫在做尾遞歸的時(shí)候，就不會(huì)去不斷創(chuàng)建新的棧幀谆棱，而是就著當(dāng)前的棧幀不斷的去覆蓋快压，一來防止棧溢出，二來節(jié)省了調(diào)用函數(shù)時(shí)創(chuàng)建棧幀的開銷垃瞧，用《算法精解》里面的原話就是：“When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack.”
問題三：尾遞歸優(yōu)化是交給編譯器還是編程人員蔫劣？
第三個(gè)問題，優(yōu)化工作交給編譯器還是交給自己个从？這個(gè)怎么說呢脉幢，據(jù)網(wǎng)上查閱，java嗦锐，C#和python都不支持編譯環(huán)境自動(dòng)優(yōu)化尾遞歸嫌松，這種情況下，當(dāng)然是別用遞歸效率最高奕污，可以看下這里萎羔。但是對于C語言來說，編譯器白提供的服務(wù)碳默，用了也不差贾陷，畢竟遞歸代碼會(huì)好理解一點(diǎn)缘眶，但換句話說，如果寫到尾遞歸這份上了髓废，變成非遞歸已經(jīng)很好實(shí)現(xiàn)了巷懈，完全可以用循環(huán)來搞定，所以呢瓦哎，這個(gè)時(shí)候砸喻，就看個(gè)人喜好了。
