Can you summarize the following document?
        
  在電腦科學,尾呼叫是指一個函式裡的最後一個動作是一個函式呼叫的情形:即這個呼叫的返回值直接被當前函式返回的情形。這種情形下稱該呼叫位置為尾位置。若這個函式在尾位置呼叫本身(或是一個尾呼叫本身的其他函式等等),則稱這種情況為尾遞迴,是遞迴的一種特殊情形。尾呼叫不一定是遞迴呼叫,但是尾遞迴特別有用,也比較容易實現。  在程式執行時,計算機會為應用程式分配一定的記憶體空間;應用程式則會自行分配所獲得的記憶體空間,其中一部分被用於記錄程式中正在呼叫的各個函式的執行情況,這就是函式的呼叫棧。常規的函式呼叫總是會在呼叫棧最上層新增一個新的堆疊幀(stack frame,也翻譯為“棧幀”或簡稱為“幀”),這個過程被稱作“入棧”或“壓棧”(意即把新的幀壓在棧頂)。當函式的呼叫層數非常多時,呼叫棧會消耗不少記憶體,甚至會撐爆記憶體空間(棧溢位),造成程式嚴重卡頓或意外崩潰。尾呼叫的呼叫棧則特別易於優化,從而可減少記憶體空間的使用,也能提高執行速度。其中,對尾遞迴情形的優化效果最為明顯,尤其是遞迴演算法非常複雜的情形。  一般來說,尾呼叫消除是可選的,可以用,也可以不用。然而,在函式程式語言中,語言標準通常會要求編譯器或執行平臺實現尾呼叫消除。這讓程式設計師可以用遞迴取代迴圈而不喪失效能。

  

  尾呼叫 (tail call) 指的是一個函式的最後一條語句也是一個返回撥用函式的語句。在函式體末尾被返回的可以是對另一個函式的呼叫,也可以是對自身呼叫(即自身遞迴呼叫)。

  尾呼叫可能位於一個函式語法上最後的位置:  在這裡,codice_1、codice_2 都是函式呼叫,但是 codice_2 是函式返回前的最後執行的東西,所以也是所謂的尾位置。然後,並非所有的尾呼叫都必須在一個函式語法上最後的位置。考慮:  在這裡,codice_4、codice_5 的呼叫都在尾位置。這是因為儘管 codice_2 不在 codice_7 語法上最後的位置,它是 codice_8 敘述其中一個分支最後的位置。  現在考慮以下程式碼:  在這裡,codice_1 處於 codice_10 的尾位置,但不處於 codice_11 或 codice_12 的尾位置。這是因為程式必須返回這2個 codice_13 函式的呼叫以檢查、更動 codice_13 的返回值。

  傳統模式的編譯器對於尾呼叫的處理方式就像處理其他普通函式呼叫一樣,總會在呼叫時建立一個新的棧幀(stack frame)並將其推入呼叫棧頂部,用於表示該次函式呼叫。  當一個函式呼叫發生時,電腦必須 “記住” 呼叫函式的位置 —— 返回位置,才可以在呼叫結束時帶著返回值回到該位置,返回位置一般存在呼叫棧上。在尾呼叫這種特殊情形中,電腦理論上可以不需要記住尾呼叫的位置而從被呼叫的函式直接帶著返回值返回撥用函式的返回位置(相當於直接連續返回兩次)。尾呼叫消除即是在不改變當前呼叫棧(也不新增新的返回位置)的情況下跳到新函式的一種優化(完全不改變呼叫棧是不可能的,還是需要校正呼叫棧上形式引數與區域性變數的資訊。)  由於當前函式幀上包含區域性變數等等大部分的東西都不需要了,當前的函式幀經過適當的更動以後可以直接當作被尾呼叫的函式的幀使用,然後程式即可以跳到被尾呼叫的函式。產生這種函式幀更動程式碼與 “jump”(而不是一般常規函式呼叫的程式碼)的過程稱作尾呼叫消除(Tail Call Elimination)或尾呼叫優化(Tail Call Optimization, TCO)。尾呼叫優化讓位於尾位置的函式呼叫跟 codice_15 語句效能一樣高,也因此使得高效的結構程式設計成為現實。  然而,對於 C++ 等語言來說,在函式最後 return g(x); 並不一定是尾遞迴——在返回之前很可能涉及到物件的解構函式,使得 g(x) 不是最後執行的那個。這可以通過返回值優化來解決。

  若函式在尾位置呼叫自身(或是一個尾呼叫本身的其他函式等等),則稱這種情況為尾遞迴。尾遞迴也是遞迴的一種特殊情形。尾遞迴是一種特殊的尾呼叫,即在尾部直接呼叫自身的遞迴函式。對尾遞迴的優化也是關注尾呼叫的主要原因。尾呼叫不一定是遞迴呼叫,但是尾遞迴特別有用,也比較容易實現。

  尾遞迴在普通尾呼叫的基礎上,多出了2個特徵:

  對函式呼叫在尾位置的遞迴或互相遞迴的函式,由於函式自身呼叫次數很多,遞迴層級很深,尾遞迴優化則使原本 O(n) 的呼叫棧空間只需要 O(1)。因此一些程式語言的標準要求語言實現進行尾呼叫消除,例如 Scheme與 ML 家族的語言。在 Scheme 中,語言標準還將尾位置形式化,指定了各種語法中允許尾呼叫的地方。  以 Python 為例,主要區分普通遞迴和尾遞迴對棧空間的使用: def recsum(x): 呼叫codice_16為例,SICP中描述了相應的棧空間變化: 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語言等語言中設計codice_17等特殊結構語句,使用迭代、尾遞迴,對普通遞迴進行優化,減少可能對記憶體的極端消耗。修改以上程式碼,可以成為尾遞迴: def tailrecsum(x, running_total=0):  或者使用迭代:  for i in range(6):  對比後者尾遞迴對記憶體的消耗:  tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15  則是線性的。

  要方便地實現尾呼叫優化,一般需藉助編譯器或執行環境提供的現成的尾遞迴優化特性,或是依賴所用程式語言能直接支援更底層的指令跳轉。

  在 Perl 裡,程式設計師可以直接用一種帶有函式名稱的 “goto” 敘述變體:codice_18 直接使用尾呼叫。  在程式語言實現中,消除尾遞迴裡的尾呼叫比消除一般的尾呼叫容易很多。舉例來說,Java 虛擬機器(JVM)的實現會消除尾遞迴裡的尾呼叫(因為重新使用了原來的呼叫棧),但是不會消除一般的尾呼叫(因為改變了的呼叫棧)。Scala 等同樣基於 JVM 平臺的語言可以有效地實現單個函式的尾遞迴優化,但是對於多個函式的相互尾遞迴就無法優化了。  JavaScript則原本不支援尾呼叫優化,到其第6代語言核心標準“ECMAScript 6”開始規定程式引擎應在嚴格模式下使用尾呼叫優化。而且ECMAScript 6限定了尾位置不含閉包的尾呼叫才能進行優化。

  

  對於直接生成彙編的編譯器,尾部呼叫消除很簡單:只要校正棧上的形參之後把 “call” 的機器碼換成一個 “jump” 的就行了。從編譯器的觀點,以下程式碼  先會被翻譯成(這是合法的 x86 彙編):  然後,尾部呼叫消除指的是將最後兩個指令以一個 “jump” 指令替換掉:  在 codice_13 函式完成的時候,它會直接返回到 codice_20 的返回地址,省去了不必要的 codice_21 指令。  函式呼叫可能帶有引數,因此生成的彙編必須確保被呼叫函式的函式幀在跳過去之前已設定好。舉例來說,若是平臺的呼叫棧除了返回位置以外還有函式引數,編譯器需要輸出調整呼叫棧的指令。在這類平臺上,考慮程式碼:  其中 codice_22、codice_23 是引數。編譯器會把這個程式碼翻譯成以下彙編:  尾部呼叫優化會將程式碼變成:  更改後的程式碼不管在執行速度或是棧空間的使用上的效能都比較好。

  由於很多 Scheme 的編譯器使用 C 作為中間目標語言,問題可轉化為如何在 C 裡在不讓棧向上增長的前提下實現尾部遞迴(假設 C 的編譯器不優化尾部呼叫)。很多實現透過一種叫做彈跳床 (計算機術語) (trampoline)的裝置,也就是一塊不斷進行函式呼叫的程式碼。所有函式程式碼的載入過程都透過這個彈跳床。當一個函式需要呼叫另一個函式時,它不是直接呼叫該函式,而是將該函式的位置、該呼叫使用的引數等資訊傳遞給彈跳床,讓愛插手的彈跳床去代為執行。這樣就可以確保 C 的棧不會向上增長並且可以讓迭代無限地繼續。  用 Groovy、Visual Basic.NET、C# 等等支援高階函式的語言實現彈跳床是可能的。

  通常被用於解釋遞迴的程式是計算階乘。以下計算階乘的 Scheme 程式不是尾端遞迴,而只是一般遞迴:  因此,如果呼叫 codice_24 時的引數 codice_25 足夠大,這一程式會出現堆疊溢位。然而,如果將同一程式寫作尾端遞迴,按 Scheme 的標準將不會出現溢位:  在第2個程式中,注意 codice_26 函式直接返回其遞迴呼叫,而沒有對其進行運算。因此,這是一個尾端遞迴,這讓直譯器或編譯器將本來是  的執行過程組合成在時間、空間上效能都較好的型態:  因為在中間過程中重複使用 codice_26 的函式幀,這種重組節省了空間。這也代表程式設計師不需要為了擔心棧空間或是堆空間用完。在一般的實現中,尾部遞迴的型態也比其他型態更快速,不過僅僅是常量倍數的差異(非指數差異)。  很多使用函式語言的程式設計師會為了使用這個優化將遞迴的程式碼寫成為尾部遞迴的形式。這通常需要一個多出來代表 “蒐集器” 的形參(上述例子的 codice_28 引數)。在一些語言中的一些函式的實現中(像是過濾一個列的實現等等),如果要使用尾部遞迴則需要將本來沒有副作用的純函式改寫成會更動其他參引的形式。
在計算機學,尾呼叫是指一個函式裡的最後一個動作是返回一個函式的呼叫結果的情形,即最後一步新呼叫的返回值直接被當前函式的返回結果。此時,該尾部呼叫位置被稱為尾位置。尾呼叫中有一種重要而特殊的情形叫做尾遞迴。經過適當處理,尾遞迴形式的函式的執行效率可以被極大地優化。尾呼叫原則上都可以通過簡化函式呼叫棧的結構而獲得效能優化(稱為“尾呼叫消除”),但是優化尾呼叫是否方便可行取決於執行環境對此類優化的支援程度如何。