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

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

中圖分類號：TP311 ? ? ?文獻標(biāo)識碼：A

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

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

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

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

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

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

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

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

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

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

尾調(diào)用優(yōu)化是從ES6才開始出現(xiàn)的概念，以JavaScript為例，尾調(diào)用優(yōu)化只有在嚴(yán)格模式（strict mode）下才有效，在正常模式下是無效的。該模式是ECMA-262規(guī)范定義的JavaScript標(biāo)準(zhǔn)，其開啟命令"use strict"在 JavaScript 1.8.5 （ECMA Script5） 中增加，發(fā)布于2009年12月。表達式"use strict"的聲明必須在腳本或函數(shù)的開頭添加。它不是一條語句，而是一個字符串字面量，在 JavaScript 舊版本中會被忽略。目前主流瀏覽器都已支持嚴(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ù)就可以輕松識別尾調(diào)用了;VC也有類似選項。不過值得指出的是，在C++、C#等語言的函數(shù)體中若存在結(jié)構(gòu)體或類的構(gòu)造，那么在調(diào)用結(jié)束返回時，由編譯器自動生成的析構(gòu)函數(shù)很可能會取代return語句的末尾位置，隱式的變?yōu)檎{(diào)用函數(shù)的“最后一個動作”，依據(jù)定義判斷這就不是尾調(diào)用了。為了解決這一問題，C++引入了一項編譯優(yōu)化技術(shù)，叫作“返回值優(yōu)化”（Return Value Optimization， RVO）?；臼侄问菍⒋祷氐膶ο髽?gòu)造在調(diào)用者的棧幀上，這樣調(diào)用者就可以直接訪問這個對象而不必復(fù)制了，自然也省去了調(diào)用析構(gòu)函數(shù)。可以認(rèn)為是強制開啟了尾調(diào)用優(yōu)化。

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

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

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

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

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

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

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

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

補充一點說明，雖然在此我們多用JS舉例，但對于C++等編程語言也完全適用。

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

注釋：

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

參考文獻：

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

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

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

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

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

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