詳解“尾遞歸”

摘要：該文首先講解了“尾調(diào)用”的概念和性質(zhì)，介紹了“尾調(diào)用優(yōu)化”的實(shí)用意義?！拔舱{(diào)用”與“遞歸”的結(jié)合，引出了“尾遞歸”。隨后以JS環(huán)境下的斐波那契數(shù)列（Fibonacci）為例探討了其使用方法與改造技巧，最后簡(jiǎn)單講述了尾遞歸優(yōu)化的實(shí)現(xiàn)原理。

關(guān)鍵詞：尾調(diào)用;優(yōu)化;遞歸;尾遞歸;柯里化

中圖分類號(hào)：TP311 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）17-0208-03

Abstract： This paper introduces the definition and character of tail call， as well as the utility of Tail Call Optimization（TCO）. The combination of tail call and recursion generates “tail recursion”. Next， I discuss the method of use and transformation skill through the example of Fibonacci in the JS programming environment. Last， the implementation principle of TCO is explained briefly.

Key words： tail call; optimization; recursion; tail recursion; currying

尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念。當(dāng)一個(gè)函數(shù)處于（另）一個(gè)函數(shù)的尾部，準(zhǔn)確地說，是在最后一條返回語(yǔ)句（return）中的時(shí)候，我們稱之為尾調(diào)用。從主調(diào)函數(shù)的角度看，執(zhí)行的最后一個(gè)動(dòng)作是返回（另）一個(gè)函數(shù)的運(yùn)行結(jié)果;從被調(diào)函數(shù)的角度看，運(yùn)行結(jié)果直接被另一個(gè)函數(shù)返回了。通常情況下，一個(gè)函數(shù)的返回值是一個(gè)簡(jiǎn)單的數(shù)值;而在尾調(diào)用中，如果不考慮遞歸的話，返回的是另一個(gè)函數(shù)的運(yùn)行結(jié)果。如：

值得注意的是，由于程序在返回時(shí)可能存在分支結(jié)構(gòu)，因此尾調(diào)用不一定是字面上的最后一條語(yǔ)句;這里的“尾”字，指的是程序執(zhí)行的最后一個(gè)動(dòng)作，我們稱該調(diào)用位置是函數(shù)的尾位置。舉個(gè)簡(jiǎn)單的例子：

不難看出，這里的尾位置是對(duì)a（）的調(diào)用和返回就不是函數(shù)x書面上的最后一條語(yǔ)句。如果情況稍復(fù)雜些，則：

這里的函數(shù)y和z都不是尾調(diào)用，即使z函數(shù)在語(yǔ)義上沒有變化。當(dāng)然，如果一個(gè)函數(shù)沒有return，也就是不返回?cái)?shù)值的話，就更談不上尾調(diào)用了。

在程序運(yùn)行時(shí)，計(jì)算機(jī)會(huì)為應(yīng)用程序分配一定的內(nèi)存空間;應(yīng)用程序則會(huì)自行分配所獲得的內(nèi)存空間，其中一部分被用于記錄程序中正在調(diào)用的各個(gè)函數(shù)的運(yùn)行情況，這就是函數(shù)的調(diào)用棧（call stack）。一般的函數(shù)調(diào)用總是會(huì)在調(diào)用棧最上層添加一個(gè)新的棧幀（stack frame），這個(gè)過程被稱作“入棧”或“壓?！保╬ush）。當(dāng)函數(shù)的調(diào)用層數(shù)非常多時(shí)，調(diào)用棧會(huì)消耗掉不少內(nèi)存，甚至?xí)伪瑮？臻g造成溢出，導(dǎo)致程序嚴(yán)重卡頓或意外崩潰。

在傳統(tǒng)的程序調(diào)用的過程中，計(jì)算機(jī)必須“記住”調(diào)用函數(shù)的返回位置，才能在調(diào)用結(jié)束后返回該位置繼續(xù)執(zhí)行后續(xù)命令，該位置信息（即下一條指令的內(nèi)存地址）一般被存放在調(diào)用棧上。與之不同的是，在尾調(diào)用這種特殊的情形中，由于調(diào)用下級(jí)函數(shù)以后上級(jí)函數(shù)就結(jié)束了，所以執(zhí)行到最后一步，計(jì)算機(jī)可以不需要記住尾調(diào)用的返回位置，而是帶著返回值直接從被調(diào)函數(shù)越級(jí)跳轉(zhuǎn)到調(diào)用函數(shù)的返回位置，相當(dāng)于連續(xù)返回了兩次，減少了棧中一次調(diào)用幀的存取，如圖1所示。

由于尾調(diào)用是外層函數(shù)的最后一步操作，尾調(diào)用返回后，外層函數(shù)也就返回了。執(zhí)行尾調(diào)用的時(shí)候，外層函數(shù)棧幀中保存的調(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了，所以，可以用內(nèi)層函數(shù)（即尾調(diào)用函數(shù)）的棧幀覆蓋外層函數(shù)的棧幀（而不是在外層函數(shù)棧幀下面再新開一個(gè)），這樣可以節(jié)省棧空間。

如果覺得有些抽象，可以舉個(gè)具體例子：

很明顯的，調(diào)用g（3）之后，函數(shù)f（）就結(jié)束了，所以當(dāng)執(zhí)行到g（3）的時(shí)候，完全可以用g（3）的棧幀覆蓋f（）的棧幀。

從原理上我們發(fā)現(xiàn)，尾調(diào)用的棧是易于優(yōu)化的。無(wú)論有多少層尾調(diào)用，都可以通過消除保持棧中的調(diào)用幀始終只有一條，從而減少內(nèi)存使用，提高運(yùn)行速度。在圖2中，func0和func1的局部變量、func1和func2的返回位置等數(shù)據(jù)都變?yōu)榱藷o(wú)用，于是可依次用func1和func2的棧幀迭代覆蓋掉func0的棧幀，而不是在func0、func1或func2棧幀外再新開一個(gè)。尾調(diào)用優(yōu)化（Tail Call Optimization， TCO）或尾調(diào)用消除（Tail Call Elimination）讓尾位置的函數(shù)返回跟goto語(yǔ)句的執(zhí)行效率一樣高，在匯編層面成功地用jmp替代了call的職能。理論上講尾調(diào)用可以通過簡(jiǎn)化函數(shù)調(diào)用棧的結(jié)構(gòu)獲得性能提升，但實(shí)際上尾調(diào)用消除是否能真正起作用決定于運(yùn)行環(huán)境是否支持此類優(yōu)化，以及編程時(shí)是否開啟這兩方面的因素。

尾調(diào)用優(yōu)化是從ES6才開始出現(xiàn)的概念，以JavaScript為例，尾調(diào)用優(yōu)化只有在嚴(yán)格模式（strict mode）下才有效，在正常模式下是無(wú)效的。該模式是ECMA-262規(guī)范定義的JavaScript標(biāo)準(zhǔn)，其開啟命令"use strict"在 JavaScript 1.8.5 （ECMA Script5） 中增加，發(fā)布于2009年12月。表達(dá)式"use strict"的聲明必須在腳本或函數(shù)的開頭添加。它不是一條語(yǔ)句，而是一個(gè)字符串字面量，在 JavaScript 舊版本中會(huì)被忽略。目前主流瀏覽器都已支持嚴(yán)格模式，如：Internet Explorer 10 +、Firefox 4+、Chrome 13+、Safari 5.1+、Opera 12+、IOS 5+、Android 3+等①。在嚴(yán)格模式下，存在諸如：不允許使用未聲明的變量，不允許刪除變量或?qū)ο?，不允許刪除函數(shù)等限制，需要注意。

如果是用GCC編譯的話，加上-O2或-O3的優(yōu)化參數(shù)就可以輕松識(shí)別尾調(diào)用了;VC也有類似選項(xiàng)。不過值得指出的是，在C++、C#等語(yǔ)言的函數(shù)體中若存在結(jié)構(gòu)體或類的構(gòu)造，那么在調(diào)用結(jié)束返回時(shí)，由編譯器自動(dòng)生成的析構(gòu)函數(shù)很可能會(huì)取代return語(yǔ)句的末尾位置，隱式的變?yōu)檎{(diào)用函數(shù)的“最后一個(gè)動(dòng)作”，依據(jù)定義判斷這就不是尾調(diào)用了。為了解決這一問題，C++引入了一項(xiàng)編譯優(yōu)化技術(shù)，叫作“返回值優(yōu)化”（Return Value Optimization， RVO）?；臼侄问菍⒋祷氐膶?duì)象構(gòu)造在調(diào)用者的棧幀上，這樣調(diào)用者就可以直接訪問這個(gè)對(duì)象而不必復(fù)制了，自然也省去了調(diào)用析構(gòu)函數(shù)?？梢哉J(rèn)為是強(qiáng)制開啟了尾調(diào)用優(yōu)化。

一般來(lái)說，尾調(diào)用消除是可選的，可以用，也可以不用。但是，在函數(shù)式編程語(yǔ)言中，語(yǔ)言標(biāo)準(zhǔn)通常會(huì)要求編譯器或運(yùn)行平臺(tái)實(shí)現(xiàn)尾調(diào)用消除，讓程序員可以用遞歸代替循環(huán)而不喪失性能。尾遞歸的優(yōu)化效果最為明顯，尤其是遞歸算法非常復(fù)雜的情形。

在尾調(diào)用中有一種特殊但重要的情況叫作尾遞歸。一般地，函數(shù)調(diào)用自身，稱為遞歸。如果是尾調(diào)用自身，就稱為尾遞歸。我們知道，遞歸作為一種解決復(fù)雜問題的方法思路，有時(shí)候比迭代更具有可讀性和可維護(hù)性，但不得不考慮棧資源的耗費(fèi);由于需要同時(shí)保存所有中間函數(shù)的調(diào)用幀，容易因壓棧過深帶來(lái)性能下降，更面臨著“棧溢出”（stack overflow）錯(cuò)誤的風(fēng)險(xiǎn)。尾遞歸很好地解決了這一矛盾——由于只存在一個(gè)調(diào)用幀，所以永遠(yuǎn)不會(huì)發(fā)生“棧溢出”的錯(cuò)誤。以累加求和為例，f（n） = f（n-1） + n; 會(huì)保存n個(gè)調(diào)用幀，而使用尾遞歸f（n， sum） = f（n-1， sum+n）; 則只需保留最后一個(gè)棧幀即可，前面的都可以刪掉，這樣復(fù)雜度也從O（n）降到了O（1）。經(jīng)過適當(dāng)處理，尾遞歸形式的函數(shù)的運(yùn)行效率可以得到極大優(yōu)化，達(dá)到與循環(huán)相當(dāng)?shù)乃?。以斐波那契?shù)列（Fibonacci）為例：

我們發(fā)現(xiàn)，尾遞歸的實(shí)現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。要做到這一點(diǎn)，就須把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)。這樣做看起來(lái)不大直觀，解決辦法有兩種：

方法1：在尾遞歸函數(shù)之外，再提供一個(gè)正常形式的函數(shù)。

方法2：函數(shù)式編程里有個(gè)術(shù)語(yǔ)叫作currying，音譯為“柯里化”，意思是將接收多參數(shù)的函數(shù)表面上轉(zhuǎn)換成只接收單參數(shù)函數(shù)的形式，實(shí)際上是返回一個(gè)用來(lái)接收余下參數(shù)的新函數(shù)的技術(shù)。聽起來(lái)有點(diǎn)繞，下面看看具體實(shí)例。

curry，其實(shí)就是我們所熟知的“咖喱”;currying，意為烹制咖喱菜。特點(diǎn)是把許多種香料（如：姜黃，胡荽籽，辣椒，孜然，小茴香，白胡椒，花椒，芥末等）分別準(zhǔn)備好后，放在一起煮，合成一道菜，有點(diǎn)像“八寶粥”的意思。用其命名，十分形象。在上例中Fibonacci傳遞n，currying調(diào)用tailFibonacci、傳遞 1， 1，最后合在一起?！翱吕锘痹诒举|(zhì)上就是一個(gè)分步處理參數(shù)的過程，可以使函數(shù)更具可讀性和彈性。見下：

前面我們已經(jīng)知道了如何將非尾遞歸函數(shù)改寫為尾遞歸的形式，以便使用尾調(diào)用優(yōu)化。進(jìn)一步的，我們來(lái)了解一下這樣的尾遞歸優(yōu)化在計(jì)算機(jī)系統(tǒng)中是如何實(shí)現(xiàn)的，這有利于我們?cè)谝恍o(wú)法使用尾調(diào)用優(yōu)化的情況下（如：ES5環(huán)境或程序不符合尾調(diào)用范式）手動(dòng)產(chǎn)生那樣的效果。

下述tail函數(shù)的精妙之處在于狀態(tài)變量active的運(yùn)用。默認(rèn)情況下，該變量是不激活的;而一旦進(jìn)入尾遞歸優(yōu)化的過程，這個(gè)變量就激活了。在上例的第一次調(diào)用后，變量active會(huì)被“激活”。于是后續(xù)每次遞歸，都只是將本次接收的參數(shù)推入stack數(shù)組，直接返回不進(jìn)入下一輪遞歸;而返回后由于stack數(shù)組里有一個(gè)數(shù)組項(xiàng)，通過while循環(huán)又處理新的參數(shù)列表，所以就會(huì)一直重復(fù)“進(jìn)入遞歸->獲得參數(shù)列表->返回->進(jìn)入遞歸->...”這樣的輪回，直到某次遞歸沒有向stack數(shù)組推入新的參數(shù)為止。如此一來(lái)就很巧妙地將“遞歸”改寫成了“循環(huán)”，后一輪的參數(shù)會(huì)取代前一輪的參數(shù)，保證調(diào)用棧永遠(yuǎn)只有一層。

補(bǔ)充一點(diǎn)說明，雖然在此我們多用JS舉例，但對(duì)于C++等編程語(yǔ)言也完全適用。

綜上所述我們看到，尾遞歸由于可通過“尾調(diào)用消除”技術(shù)予以簡(jiǎn)化，從而具有不同于一般遞歸的重要性。本文系統(tǒng)闡述了尾遞歸的優(yōu)化原理、使用方法和構(gòu)造技巧，熟練掌握并靈活運(yùn)用將會(huì)給編程愛好者帶來(lái)不小的啟發(fā)和幫助。

注釋：

① 引自網(wǎng)站”Can I use... Support tables for HTML5， CSS3， etc，https：//caniuse.com/#feat=use-strict.

參考文獻(xiàn)：

[1] 方悅. 循環(huán)、迭代與遞歸[J]. 電腦知識(shí)與技術(shù)， 2020， 16（6）： 55-57， 66.

[2] 阮一峰. ECMAScript 6 入門[M]. 北京： 電子工業(yè)出版社， 2014.

[3] 崔蕊. 遞歸到非遞歸算法的轉(zhuǎn)換[J]. 電腦知識(shí)與技術(shù)， 2009， 5（23）： 6424-6425， 6458.

[4] 張國(guó). 基于遞歸算法的非遞歸實(shí)現(xiàn)研究[J]. 長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)版）理工卷， 2009， 6（3）： 223-225.

[5] 高漢平， 方志雄. 從遞歸算法到非遞歸的變換[J]. 黃岡師范學(xué)院學(xué)報(bào)， 2002， 22（3）： 47-50.

【通聯(lián)編輯：謝媛媛】