詳解“尾遞歸”

摘要：該文首先講解了“尾調用”的概念和性質，介紹了“尾調用優化”的實用意義。“尾調用”與“遞歸”的結合，引出了“尾遞歸”。隨后以JS環境下的斐波那契數列（Fibonacci）為例探討了其使用方法與改造技巧，最后簡單講述了尾遞歸優化的實現原理。

關鍵詞：尾調用;優化;遞歸;尾遞歸;柯里化

中圖分類號：TP311 ? ? ?文獻標識碼：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

尾調用（Tail Call）是函數式編程的一個重要概念。當一個函數處于（另）一個函數的尾部，準確地說，是在最后一條返回語句（return）中的時候，我們稱之為尾調用。從主調函數的角度看，執行的最后一個動作是返回（另）一個函數的運行結果;從被調函數的角度看，運行結果直接被另一個函數返回了。通常情況下，一個函數的返回值是一個簡單的數值;而在尾調用中，如果不考慮遞歸的話，返回的是另一個函數的運行結果。如：

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

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

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

在程序運行時，計算機會為應用程序分配一定的內存空間;應用程序則會自行分配所獲得的內存空間，其中一部分被用于記錄程序中正在調用的各個函數的運行情況，這就是函數的調用棧（call stack）。一般的函數調用總是會在調用棧最上層添加一個新的棧幀（stack frame），這個過程被稱作“入棧”或“壓棧”（push）。當函數的調用層數非常多時，調用棧會消耗掉不少內存，甚至會撐爆棧空間造成溢出，導致程序嚴重卡頓或意外崩潰。

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

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

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

很明顯的，調用g（3）之后，函數f（）就結束了，所以當執行到g（3）的時候，完全可以用g（3）的棧幀覆蓋f（）的棧幀。

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

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

如果是用GCC編譯的話，加上-O2或-O3的優化參數就可以輕松識別尾調用了;VC也有類似選項。不過值得指出的是，在C++、C#等語言的函數體中若存在結構體或類的構造，那么在調用結束返回時，由編譯器自動生成的析構函數很可能會取代return語句的末尾位置，隱式的變為調用函數的“最后一個動作”，依據定義判斷這就不是尾調用了。為了解決這一問題，C++引入了一項編譯優化技術，叫作“返回值優化”（Return Value Optimization， RVO）。基本手段是將待返回的對象構造在調用者的棧幀上，這樣調用者就可以直接訪問這個對象而不必復制了，自然也省去了調用析構函數。可以認為是強制開啟了尾調用優化。

一般來說，尾調用消除是可選的，可以用，也可以不用。但是，在函數式編程語言中，語言標準通常會要求編譯器或運行平臺實現尾調用消除，讓程序員可以用遞歸代替循環而不喪失性能。尾遞歸的優化效果最為明顯，尤其是遞歸算法非常復雜的情形。

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

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

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

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

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

前面我們已經知道了如何將非尾遞歸函數改寫為尾遞歸的形式，以便使用尾調用優化。進一步的，我們來了解一下這樣的尾遞歸優化在計算機系統中是如何實現的，這有利于我們在一些無法使用尾調用優化的情況下（如：ES5環境或程序不符合尾調用范式）手動產生那樣的效果。

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

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

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

注釋：

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

參考文獻：

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

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

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

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

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

【通聯編輯：謝媛媛】