|
尾遞歸（tail recursive），看名字就知道是某種形式的遞歸。簡(jiǎn)單的說(shuō)遞歸就是函數(shù)自己調(diào)用自己。那尾遞歸和遞歸之間的差別就只能體現(xiàn)在參數(shù)上了。
尾遞歸wiki解釋如下：
尾部遞歸是一種編程技巧。遞歸函數(shù)是指一些會(huì)在函數(shù)內(nèi)調(diào)用自己的函數(shù)，如果在遞歸函數(shù)中，遞歸調(diào)用返回的結(jié)果總被直接返回，則稱為尾部遞歸。尾部遞歸的函數(shù)有助將算法轉(zhuǎn)化成函數(shù)編程語(yǔ)言，而且從編譯器角度來(lái)說(shuō)，亦容易優(yōu)化成為普通循環(huán)。這是因?yàn)閺碾娔X的基本面來(lái)說(shuō)，所有的循環(huán)都是利用重復(fù)移跳到代碼的開(kāi)頭來(lái)實(shí)現(xiàn)的。如果有尾部歸遞，就只需要疊套一個(gè)堆棧，因?yàn)殡娔X只需要將函數(shù)的參數(shù)改變?cè)僦匦抡{(diào)用一次。利用尾部遞歸最主要的目的是要優(yōu)化，例如在Scheme語(yǔ)言中，明確規(guī)定必須針對(duì)尾部遞歸作優(yōu)化。可見(jiàn)尾部遞歸的作用，是非常依賴于具體實(shí)現(xiàn)的。
我們還是從簡(jiǎn)單的斐波那契開(kāi)始了解尾遞歸吧。
用普通的遞歸計(jì)算Fibonacci數(shù)列：
10 | printf("請(qǐng)輸入斐波那契數(shù)n："); |
28 | return factorial(n-1) + factorial(n-2); |
程序員運(yùn)行結(jié)果如下：
4 | Process returned 0 (0x0) execution time : 3.502 s |
5 | Press any key to continue. |
在i5的CPU下也要花費(fèi) 3.502 秒的時(shí)間。
下面我們看看如何用尾遞歸實(shí)現(xiàn)斐波那契數(shù)。
10 | printf("請(qǐng)輸入斐波那契數(shù)n："); |
13 | rs = factorial_tail(n, 1, 1); |
19 | int factorial_tail(int n,int acc1,int acc2) |
27 | return factorial_tail(n-1,acc2,acc1+acc2); |
程序員運(yùn)行結(jié)果如下：
3 | Process returned 0 (0x0) execution time : 1.460 s |
4 | Press any key to continue. |
快了一倍有多。當(dāng)然這是不完全統(tǒng)計(jì)，有興趣的話可以自行計(jì)算大規(guī)模的值，這里只是介紹尾遞歸而已。
我們可以打印一下程序的執(zhí)行過(guò)程，函數(shù)加入下面的打印語(yǔ)句：
01 | int factorial_tail(int n,int acc1,int acc2) |
09 | printf("factorial_tail(%d, %d, %d) \n",n-1,acc2,acc1+acc2); |
10 | return factorial_tail(n-1,acc2,acc1+acc2); |
程序運(yùn)行結(jié)果：
01 | 請(qǐng)輸入斐波那契數(shù)n：10 |
02 | factorial_tail(9, 1, 2) |
03 | factorial_tail(8, 2, 3) |
04 | factorial_tail(7, 3, 5) |
05 | factorial_tail(6, 5, 8) |
06 | factorial_tail(5, 8, 13) |
07 | factorial_tail(4, 13, 21) |
08 | factorial_tail(3, 21, 34) |
09 | factorial_tail(2, 34, 55) |
10 | factorial_tail(1, 55, 89) |
12 | Process returned 0 (0x0) execution time : 1.393 s |
13 | Press any key to continue. |
從上面的調(diào)試就可以很清晰地看出尾遞歸的計(jì)算過(guò)程了。acc1就是第n個(gè)數(shù)，而acc2就是第n與第n+1個(gè)數(shù)的和，這就是我們前面講到的“迭代”的精髓，計(jì)算結(jié)果參與到下一次的計(jì)算，從而減少很多重復(fù)計(jì)算量。
fibonacci(n-1,acc2,acc1+acc2)真是神來(lái)之筆，原本樸素的遞歸產(chǎn)生的棧的層次像二叉樹(shù)一樣，以指數(shù)級(jí)增長(zhǎng)，但是現(xiàn)在棧的層次卻像是數(shù)組，變成線性增長(zhǎng)了，實(shí)在是奇妙，總結(jié)起來(lái)也很簡(jiǎn)單，原本棧是先擴(kuò)展開(kāi)，然后邊收攏邊計(jì)算結(jié)果，現(xiàn)在卻變成在調(diào)用自身的同時(shí)通過(guò)參數(shù)來(lái)計(jì)算。
小結(jié)
尾遞歸的本質(zhì)是：將單次計(jì)算的結(jié)果緩存起來(lái)，傳遞給下次調(diào)用，相當(dāng)于自動(dòng)累積。
在Java等命令式語(yǔ)言中，尾遞歸使用非常少見(jiàn)，因?yàn)槲覀兛梢灾苯佑醚h(huán)解決。而在函數(shù)式語(yǔ)言中，尾遞歸卻是一種神器，要實(shí)現(xiàn)循環(huán)就靠它了。
很多人可能會(huì)有疑問(wèn)，為什么尾遞歸也是遞歸，卻不會(huì)造成棧溢出呢？因?yàn)榫幾g器通常都會(huì)對(duì)尾遞歸進(jìn)行優(yōu)化。編譯器會(huì)發(fā)現(xiàn)根本沒(méi)有必要存儲(chǔ)棧信息了，因而會(huì)在函數(shù)尾直接清空相關(guān)的棧。
|
