尾調用
在計算機學裡，尾調用是指一個函數裡的最後一個動作是返回一個函數的調用結果的情形，即最後一步新調用的返回值直接作為當前函數的返回結果。[1]此時，該尾部調用位置被稱為尾位置。尾調用中有一種重要而特殊的情形叫做尾遞歸。經過適當處理，尾遞歸形式的函數的運行效率可以被極大地優化。[1]尾調用原則上都可以通過簡化函數調用棧的結構而獲得性能優化（稱為「尾調用消除」），但是優化尾調用是否方便可行取決於運行環境對此類優化的支持程度如何。
概述
編輯在計算機科學裡，尾調用是指一個函數裡的最後一個動作是一個函數調用的情形：即這個調用的返回值直接被當前函數返回的情形。這種情形下稱該調用位置為尾位置。若這個函數在尾位置調用本身（或是一個尾調用本身的其他函數等等），則稱這種情況為尾遞歸，是遞歸的一種特殊情形。尾調用不一定是遞歸調用，但是尾遞歸特別有用，也比較容易實現。
在程序運行時，計算機會為應用程序分配一定的內存空間；應用程序則會自行分配所獲得的內存空間，其中一部分被用於記錄程序中正在調用的各個函數的運行情況，這就是函數的調用棧。常規的函數調用總是會在調用棧最上層添加一個新的堆棧幀（stack frame，也翻譯為「棧幀」或簡稱為「幀」），這個過程被稱作「入棧」或「壓棧」（意即把新的幀壓在棧頂）。當函數的調用層數非常多時，調用棧會消耗不少內存，甚至會撐爆內存空間（棧溢出）[1]，造成程序嚴重卡頓或意外崩潰。尾調用的調用棧則特別易於優化，從而可減少內存空間的使用，也能提高運行速度。[1]其中，對尾遞歸情形的優化效果最為明顯，尤其是遞歸算法非常複雜的情形。[1]
一般來說，尾調用消除是可選的，可以用，也可以不用。然而，在函數編程語言中，語言標準通常會要求編譯器或運行平台實現尾調用消除。這讓程序員可以用遞歸取代循環而不喪失性能。
定義與說明
編輯定義
編輯尾調用 （tail call） 指的是一個函數的最後一條語句也是一個返回調用函數的語句。在函數體末尾被返回的可以是對另一個函數的調用，也可以是對自身調用（即自身遞歸調用）。[1]
特徵與簡單示例
編輯尾調用可能位於一個函數語法上最後的位置：
function foo(data) {
a(data);
return b(data);
}
在這裡，a(data)、b(data) 都是函數調用，但是 b(data) 是函式返回前的最後運行的東西，所以也是所謂的尾位置。然後，並非所有的尾調用都必須在一個函數語法上最後的位置。考慮：
function bar(data) {
if ( a(data) ) {
return b(data);
}
return c(data);
}
在這裡，b、c 的調用都在尾位置。這是因為儘管 b(data) 不在 bar 語法上最後的位置，它是 if 敘述其中一個分支最後的位置。
現在考慮以下代碼：
function foo1(data) {
return a(data) + 1;
}
function foo2(data) {
var ret = a(data);
return ret;
}
function foo3(data) {
var ret = a(data);
return (ret === 0) ? 1 : ret;
}
在這裡，a(data) 處於 foo2 的尾位置，但不處於 foo1 或 foo3 的尾位置。這是因為程序必須返回這2個 a 函數的調用以檢查、更動 a 的返回值。
說明
編輯傳統模式的編譯器對於尾調用的處理方式就像處理其他普通函數調用一樣，總會在調用時創建一個新的棧幀（stack frame）並將其推入調用棧頂部，用於表示該次函數調用。[1]
當一個函數調用發生時，電腦必須 「記住」 調用函數的位置 —— 返回位置，才可以在調用結束時帶着返回值回到該位置，返回位置一般存在調用棧上。在尾調用這種特殊情形中，電腦理論上可以不需要記住尾調用的位置而從被調用的函數直接帶着返回值返回調用函數的返回位置（相當於直接連續返回兩次）。尾調用消除即是在不改變當前調用棧（也不添加新的返回位置）的情況下跳到新函數的一種優化（完全不改變調用棧是不可能的，還是需要校正調用棧上形式參數與局部變量的信息。[2]）
由於當前函數幀上包含局部變量等等大部分的東西都不需要了，當前的函數幀經過適當的更動以後可以直接當作被尾調用的函數的幀使用，然後程序即可以跳到被尾調用的函數。產生這種函數幀更動代碼與 「jump」（而不是一般常規函數調用的代碼）的過程稱作尾調用消除（Tail Call Elimination）或尾調用優化（Tail Call Optimization，TCO）。尾調用優化讓位於尾位置的函數調用跟 goto 語句性能一樣高，也因此使得高效的結構編程成為現實。
然而，對於 C++ 等語言來說，在函數最後 return g(x); 並不一定是尾遞歸——在返回之前很可能涉及到對象的析構函數，使得 g(x) 不是最後執行的那個。這可以通過返回值優化來解決。
尾遞歸
編輯若函數在尾位置調用自身（或是一個尾調用本身的其他函數等等），則稱這種情況為尾遞歸。尾遞歸也是遞歸的一種特殊情形。尾遞歸是一種特殊的尾調用，即在尾部直接調用自身的遞歸函數。對尾遞歸的優化也是關注尾調用的主要原因。尾調用不一定是遞歸調用，但是尾遞歸特別有用，也比較容易實現。
特點
編輯尾遞歸在普通尾調用的基礎上，多出了2個特徵：
- 在尾部調用的是函數自身 （Self-called）；
- 可通過優化，使得計算僅占用常量棧空間 (Stack Space)。
優化尾遞歸的分析與示例
編輯對函數調用在尾位置的遞歸或互相遞歸的函數，由於函數自身調用次數很多，遞歸層級很深，尾遞歸優化則使原本 O(n) 的調用棧空間只需要 O(1)。因此一些編程語言的標準要求語言實現進行尾調用消除，例如 Scheme[3][4]與 ML 家族的語言。在 Scheme 中，語言標準還將尾位置形式化，指定了各種語法中允許尾調用的地方[5]。
以 Python 為例，主要區分普通遞歸和尾遞歸對棧空間的使用[6][需要較佳來源]：
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)
調用recsum(5)為例，SICP中描述了相應的棧空間變化[7]：
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
可觀察，堆棧從左到右，增加到一個峰值後再計算從右到左縮小，這往往是我們不希望的，所以在C語言等語言中設計for, while, goto等特殊結構語句，使用迭代、尾遞歸，對普通遞歸進行優化，減少可能對內存的極端消耗。修改以上代碼，可以成為尾遞歸：
def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)
或者使用迭代：
for i in range(6):
sum += i
對比後者尾遞歸對內存的消耗：
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
則是線性的。
優化尾調用的不同方式
編輯要方便地實現尾調用優化，一般需藉助編譯器或運行環境提供的現成的尾遞歸優化特性，或是依賴所用程序語言能直接支持更底層的指令跳轉。
利用運行平台的支持直接實現
編輯在 Perl 里，程序員可以直接用一種帶有函數名稱的 「goto」 敘述變體：goto &NAME; 直接使用尾調用[8]。
在程序語言實現中，消除尾遞歸里的尾調用比消除一般的尾調用容易很多。舉例來說，Java 虛擬機（JVM）的實現會消除尾遞歸里的尾調用（因為重新使用了原來的調用棧），但是不會消除一般的尾調用（因為改變了的調用棧）。Scala 等同樣基於 JVM 平台的語言可以有效地實現單個函數的尾遞歸優化，但是對於多個函數的相互尾遞歸就無法優化了。
JavaScript則原本不支持尾調用優化，到其第6代語言核心標準「ECMAScript 6」開始規定程序引擎應在嚴格模式下使用尾調用優化。而且ECMAScript 6限定了尾位置不含閉包的尾調用才能進行優化。[1]
動手實現的方案
編輯匯編重組
編輯對於直接生成匯編的編譯器，尾部調用消除很簡單：只要校正棧上的形參之後把 「call」 的機器碼換成一個 「jump」 的就行了。從編譯器的觀點，以下代碼
function foo() return a()
先會被翻譯成（這是合法的 x86 匯編）：
foo: call a ret
然後，尾部調用消除指的是將最後兩個指令以一個 「jump」 指令替換掉：
foo: jmp a
在 a 函數完成的時候，它會直接返回到 foo 的返回地址，省去了不必要的 ret 指令。
函數調用可能帶有參數，因此生成的匯編必須確保被調用函數的函數幀在跳過去之前已設置好。舉例來說，若是平台的調用棧除了返回位置以外還有函數參數，編譯器需要輸出調整調用棧的指令。在這類平台上，考慮代碼：
function foo(data1, data2) a(data1) return b(data2)
其中 data1、data2 是參數。編譯器會把這個代碼翻譯成以下匯編：
foo: mov reg,[sp+data1] ; 透过栈指针（sp）取得 data1 并放到暂用暂存器。 push reg ; 将 data1 放到栈上以便 a 使用。 call a ; a 使用 data1。 pop ; 把 data1 從栈上拿掉。 mov reg,[sp+data2] ; 透过栈指針（sp）取得 data2 並放到暂用暂存器。 push reg ; 将 data2 放到栈上以便 b 使用。 call b ; b 使用 data2。 pop ; 把 data2 從栈上拿掉。 ret
尾部調用優化會將代碼變成：
foo: mov reg,[sp+data1] ; 透过栈指针（sp）取得 data1 并放到暂用暂存器。 push reg ; 将 data1 放到栈上以便 a 使用。 call a ; a 使用 data1。 pop ; 把 data1 從栈上拿掉。 mov reg,[sp+data2] ; 透过栈指針（sp）取得 data2 並放到暂用暂存器。 mov [sp+data1],reg ; 把 data2 放到 b 预期的位置。 jmp b ; b 使用 data2 並返回到调用 foo 的函数。
更改後的代碼不管在執行速度或是棧空間的使用上的效能都比較好。
透過彈跳床
編輯由於很多 Scheme 的編譯器使用C語言作為中間目標語言，問題可轉化為如何在 C 里在不讓棧向上增長的前提下實現尾部遞歸（假設 C 的編譯器不優化尾部調用）。很多實現透過一種叫做彈跳床（trampoline）的裝置，也就是一塊不斷進行函數調用的代碼。所有函數代碼的加載過程都透過這個彈跳床。當一個函數需要調用另一個函數時，它不是直接調用該函數，而是將該函數的位置、該調用使用的參數等信息傳遞給彈跳床，讓愛插手的彈跳床去代為執行。這樣就可以確保 C 的棧不會向上增長並且可以讓迭代無限地繼續。
用 Groovy、Visual Basic .NET、C# 等等支持高階函數的語言實現彈跳床是可能的[9]。
對所有函數調用使用彈跳床，相比常規的C調用有着高昂的開銷，所以至少有一個Scheme編譯器即Chicken，使用了首先由Henry Baker聽從Andrew Appel未發表建議而描述的一種技術[10]。在其中使用常規的C調用，但是在每次調用前檢查棧的大小。當棧達到它的最大允許大小的時候，在棧上的對象經由Cheney算法而被垃圾回收，所有存活數據都將移動到分立的堆之內。隨後棧被回縮（彈出），而程序恢復到緊鄰垃圾回收之前保存的狀態。Baker聲稱：「Appel的方法通過偶爾的跳下帝國大廈而避免了大量的小型蹦床彈跳」[10]。垃圾回收確保了相互尾遞歸可以無限的繼續。但是這種方法要求C函數調用都永不返回，因為不能保證它的調用者的棧幀仍然存在；故而它涉及到對程序代碼的更加戲劇性的內部重寫，即將其改為續體傳遞風格。
更多實例
編輯通常被用於解釋遞迴的程式是計算階乘。以下計算階乘的 Scheme 程式不是尾端遞迴，而只是一般遞迴[11]：
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
因此，如果呼叫 factorial 時的參數 n 足夠大，這一程式會出現堆疊溢位。然而，如果將同一程式寫作尾端遞迴，按 Scheme 的標準將不會出現溢位[11]：
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
在第2個程式中，注意 iter 函數直接返回其遞迴呼叫，而沒有對其進行運算。因此，這是一個尾端遞迴，這讓直譯器或編譯器將本來是
call factorial (3)
call iter (3 1)
call iter (2 3)
call iter (1 6)
call iter (0 6)
return 6
return 6
return 6
return 6
return 6
的執行過程組合成在時間、空間上性能都較好的型態：
call factorial (3) call iter (3 1) 将参数变为 (2 3)，跳至 "iter" 将参数变为 (1 6)，跳至 "iter" 将参数变为 (0 6)，跳至 "iter" return 6 return 6
因為在中間過程中重複使用 iter 的函數幀，這種重組節省了空間。這也代表程序員不需要為了擔心棧空間或是堆空間用完。在一般的實現中，尾部遞歸的型態也比其他型態更快速，不過僅僅是常量倍數的差異（非指數差異）。
很多使用函數語言的程序員會為了使用這個優化將遞歸的代碼寫成為尾部遞歸的形式。這通常需要一個多出來代表 「搜集器」 的形參（上述例子的 product 參數）。在一些語言中的一些函數的實現中（像是過濾一個列的實現等等），如果要使用尾部遞歸則需要將本來沒有副作用的純函數改寫成會更動其他參引的形式[來源請求]。
注釋與資料
編輯註釋
編輯- ^ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Nicholas C. Zakas. 第3章“Functions”第9节“Tail Call Optimization”. Understanding ECMAScript 6 [理解ES6] 1. 245 8th Street, San Francisco, CA 94103: No Starch Press. 2016: 61–64. ISBN 978-1-59327-757-4 （英語）.
- ^ recursion - Stack memory usage for tail calls - Theoretical Computer Science. Cstheory.stackexchange.com. 2011-07-29 [2013-03-21]. （原始內容存檔於2012-07-11） （英語）.
- ^ Revised^6 Report on the Algorithmic Language Scheme. R6rs.org. [2013-03-21]. （原始內容存檔於2013-05-06）.
- ^ Revised^6 Report on the Algorithmic Language Scheme - Rationale. R6rs.org. [2013-03-21]. （原始內容存檔於2013-11-11）.
- ^ Revised^6 Report on the Algorithmic Language Scheme. R6rs.org. [2013-03-21]. （原始內容存檔於2018-03-15）.
- ^ Python並沒有優化尾遞歸調用功能（以實現真正的尾遞歸特性），這裡只是用Python的語法來模擬描述尾遞歸的語法。參見Does Python optimize tail-reccursion? （頁面存檔備份，存於網際網路檔案館）
- ^ 見《計算機程序的構造和解釋》第1章第2節「Procedure and Their Computation」。
- ^ Contact details. goto. perldoc.perl.org. [2013-03-21]. （原始內容存檔於2013-03-28）.
- ^ Samuel Jack, Bouncing on your tail （頁面存檔備份，存於網際網路檔案館）. Functional Fun. April 9, 2008.
- ^ 10.0 10.1 Henry Baker, "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." （頁面存檔備份，存於網際網路檔案館）
- ^ 11.0 11.1 見《計算機程序的構造和解釋》。[頁碼請求]
引用
編輯- Harold Abelson, Gerald Jay Sussman, Julie Sussman. Structure and Interpretation of Computer Programs [計算機程序的構造和解釋]. Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0. （原始內容存檔於2018年3月9日） （英語）.