基本介紹
- 中文名：尾調用
- 位置：尾位置
- 特殊情形：尾遞歸
- 領域：計算機
概述,定義與說明,定義,特徵與簡單示例,說明,尾遞歸,概述,特點,最佳化尾調用的不同方式,利用運行平台的支持直接實現,透過彈跳床,
概述
在計算機科學里，尾調用是指一個函數裡的最後一個動作是一個函式調用的情形：即這個調用的返回值直接被當前函式返回的情形。這種情形下稱該調用位置為尾位置。若這個函式在尾位置調用本身（或是一個尾調用本身的其他函式等等），則稱這種情況為尾遞歸，是遞歸的一種特殊情形。尾調用不一定是遞歸調用，但是尾遞歸特別有用，也比較容易實現。
在程式運行時，計算機會為應用程式分配一定的記憶體空間；應用程式則會自行分配所獲得的記憶體空間，其中一部分被用於記錄程式中正在調用的各個函式的運行情況，這就是函式的調用棧。常規的函式調用總是會在調用棧最上層添加一個新的堆疊幀（stack frame，也翻譯為“棧幀”或簡稱為“幀”），這個過程被稱作“入棧”或“壓棧”（意即把新的幀壓在棧頂）。當函式的調用層數非常多時，調用棧會消耗不少記憶體，甚至會撐爆記憶體空間（棧溢出），造成程式嚴重卡頓或意外崩潰。尾調用的調用棧則特別易於最佳化，從而可減少記憶體空間的使用，也能提高運行速度。其中，對尾遞歸情形的最佳化效果最為明顯，尤其是遞歸算法非常複雜的情形。
定義與說明
定義
尾調用 (tail call) 指的是一個函式的最後一條語句也是一個返回調用函式的語句。在函式體末尾被返回的可以是對另一個函式的調用，也可以是對自身調用（即自身遞歸調用）。
特徵與簡單示例
尾調用可能位於一個函式語法上最後的位置：
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）並將其推入調用棧頂部，用於表示該次函式調用。
當一個函式調用發生時，計算機必須 “記住” 調用函式的位置 —— 返回位置，才可以在調用結束時帶著返回值回到該位置，返回位置一般存在調用棧上。在尾調用這種特殊情形中，計算機理論上可以不需要記住尾調用的位置而從被調用的函式直接帶著返回值返回調用函式的返回位置（相當於直接連續返回兩次）。尾調用消除即是在不改變當前調用棧（也不添加新的返回位置）的情況下跳到新函式的一種最佳化（完全不改變調用棧是不可能的，還是需要校正調用棧上形式參數與局部變數的信息。）
由於當前函式幀上包含局部變數等等大部分的東西都不需要了，當前的函式幀經過適當的更動以後可以直接當作被尾調用的函式的幀使用，然後程式即可以跳到被尾調用的函式。產生這種函式幀更動代碼與 “jump”（而不是一般常規函式調用的代碼）的過程稱作尾調用消除(Tail Call Elimination)或尾調用最佳化(Tail Call Optimization, TCO)。尾調用最佳化讓位於尾位置的函式調用跟goto語句性能一樣高，也因此使得高效的結構編程成為現實。
尾遞歸
概述
若函式在尾位置調用自身（或是一個尾調用本身的其他函式等等），則稱這種情況為尾遞歸。尾遞歸也是遞歸的一種特殊情形。尾遞歸是一種特殊的尾調用，即在尾部直接調用自身的遞歸函式。對尾遞歸的最佳化也是關注尾調用的主要原因。尾調用不一定是遞歸調用，但是尾遞歸特別有用，也比較容易實現。
特點
尾遞歸在普通尾調用的基礎上，多出了2個特徵：
- 在尾部調用的是函式自身 (Self-called)；
- 可通過最佳化，使得計算僅占用常量棧空間 (Stack Space)。
最佳化尾調用的不同方式
要方便地實現尾調用最佳化，一般需藉助編譯器或運行環境提供的現成的尾遞歸最佳化特性，或是依賴所用程式語言能直接支持更底層的指令跳轉。
利用運行平台的支持直接實現
在Perl里，程式設計師可以直接用一種帶有函式名稱的 “goto” 敘述變體：goto &NAME;直接使用尾調用。
在程式語言實現中，消除尾遞歸里的尾調用比消除一般的尾調用容易很多。舉例來說，Java 虛擬機（JVM）的實現會消除尾遞歸里的尾調用（因為重新使用了原來的調用棧），但是不會消除一般的尾調用（因為改變了的調用棧）。Scala等同樣基於 JVM 平台的語言可以有效地實現單個函式的尾遞歸最佳化，但是對於多個函式的相互尾遞歸就無法最佳化了。
JavaScript則原本不支持尾調用最佳化，到其第6代語言核心標準“ECMAScript 6”開始規定程式引擎應在嚴格模式下使用尾調用最佳化。而且ECMAScript 6限定了尾位置不含閉包的尾調用才能進行最佳化。
