這是Jerry 2021年的第 12 篇文章，也是汪子熙公衆号總共第 283 篇原創文章。
今天是2021年1月20日，看看曆史上的今天都發生了什麼。
2004年1月20日，第一個公開版本的Scala釋出。
Scala是一種采用靜态類型系統的編譯型語言，具有很強的可擴充性(Scalability)，這也是其名稱的由來。
Scala設計初衷是內建面向對象程式設計和函數式程式設計的各種特性，運作于JVM平台上，并相容已有的Java程式。
Jerry沒有在SAP标準産品開發中使用過Scala，隻是完成2015年公司一個内部教育訓練布置的課程作業中，使用Scala在Spark上開發了一個最簡單的demo：統計海量英文圖書裡，計算出使用頻率最高的十大單詞。
Spark是一個使用Scala程式設計語言實作的專為大規模資料處理而設計的快速通用的計算引擎。本文不會讨論Spark，而是從Scala語言裡，下圖第11行的注解@tailrec談起：尾遞歸(Tail Recursion).
每個程式員對遞歸的概念都耳熟能詳，那什麼是尾遞歸呢？
顧名思義，如果一個函數中遞歸形式的調用，出現在函數的末尾，且除了該遞歸調用外，不包含其他的運算操作，則我們稱該遞歸函數是尾遞歸函數。
本文用階乘算法來介紹尾遞歸的概念。
下圖紅色區域内是階乘算法的正常遞歸實作，藍色區域是階乘算法的尾遞歸實作版本。在正常遞歸算法的末尾，第8行語句(綠色)，除了遞歸調用factorial函數外，還包含一個同n的乘法操作，是以整個函數factorial不能算作尾遞歸函數。
而尾遞歸版本中，第14行函數末尾(黃色)，僅僅包含函數本身的遞歸調用，是以整個函數tailFactorial是一個尾遞歸函數。
尾遞歸函數存在的意義是什麼呢？要回答這個問題，我們可以先在單步調試模式下，觀察正常遞歸函數的執行過程。
我們首先使用正常遞歸函數，計算5的階乘。
輸入參數n為5，執行到第7行，5的階乘等于5乘以4的階乘。單步調試進去，輸入參數n = 5, 進入第7行，準備執行 5 * factorial(4) .
注意觀察下圖的Call Stack清單，此時我們已經有兩個factorial函數的調用棧幀了。
什麼是棧幀？複習一下大學計算機原理學到的知識：在函數執行過程中，每一個函數調用都會把目前函數的調用資訊和内部變量儲存在棧裡面，稱為一個棧幀(Stack Frame).
其中下圖序号為1的棧幀，儲存了n = 5的計算上下文；序号為2的棧幀即目前最頂層的棧幀，儲存了n = 4的計算上下文
因為隻有當n = 1時遞歸才會結束，而目前n = 4，是以繼續單步調試第7行：又生成了一個n = 3的棧幀：
n = 2：
終于我們來到了n = 1的上下文。看下圖Call Stack裡的棧幀清單，最頂層的棧幀代表目前n = 1的計算上下文。此時我們已經知道n = 1的階乘結果如何計算了，即為1本身。
第5行代碼傳回1的階乘計算結果1，這行語句傳回之後，目前序号為5的棧幀就會被銷毀，即将回到下一層序号為4的棧幀去。
此時隻剩4個棧幀了，最頂層代表n = 2的棧幀。因為現在1的階乘結果已經出來了，是以2的階乘結果也能計算了，為2乘以1.
的階乘傳回後，現在隻剩3個棧幀，最頂層為n = 3的計算上下文。3的階乘也能計算了，為3乘以前一個棧幀傳回的計算結果，即2的階乘結果，是以最後為3 × 2 = 6. 如下圖所示：
4的階乘計算，此時隻剩兩個棧幀：
5的計算結果，回到最初最先被壓到堆棧底部的n = 5的棧幀。計算完畢，5的階乘為120.
是不是展現出了《資料結構》教科書上關于棧“先進後出”的工作原理？
下面再來看看用尾遞歸實作的階乘。
下圖第20行語句是以尾遞歸方式計算5的階乘入口，調用尾遞歸函數tailFactorial，注意函數的第二個輸入參數total，這個參數用于存儲目前階乘的計算結果。
這個尾遞歸函數的結束條件是，當第一個輸入參數n為1時，就把第二個輸入參數的值，作為階乘運算的最終結果傳回。第二個參數實際上存放的，是目前遞歸調用的階乘計算結果。
當n大于1時，遞歸尚未滿足退出條件，此時首先将n和目前的階乘計算結果(變量total)相乘，将乘積作為第二個輸入參數，傳遞到下一層遞歸調用的棧幀中去。
下圖是tailFactorial函數内部，即将進入第一輪遞歸調用的棧幀：
第一輪遞歸調用的棧幀内部，序号為2.
注意，此時序号為1的棧幀已經完全不再需要了，因為我們繼續進行遞歸調用的所需資訊，都已經包含在第16行tailFactorial調用的兩個輸入參數裡了，此時n為上一層遞歸調用傳入的5 - 1 = 4，total為上一輪傳入的5 × 1 = 5. 進行下一輪遞歸調用，兩個輸入參數的值分别是4 - 1 = 3和4 * 5 = 20.
進入第三層遞歸調用，此時輸入參數 n = 3，total = 20，均為上一層調用傳入。
注意，下圖示号為1和2的兩個棧幀，實際上不再需要了，因為要繼續進行遞歸調用的所有輸入資訊，都已經存儲在标号為3的棧幀裡了：
n = 2， total = 60，同理，标号為1，2，3的棧幀都不再需要了。
n = 1，total = 120，終于計算結束了！這就是5的階乘，如何通過尾遞歸的方式計算出來的全過程。
我們在标号為5的棧幀裡得到了最終的結果，而此時雖然棧幀1～4還存在，但實際上已經毫無用處了。
因為按照尾遞歸版本的階乘實作，每一輪階乘的遞歸計算結果，已經通過第二個參數total儲存了下來，是以沒有必要再用一個完整的棧幀，去儲存目前這輪遞歸計算的函數調用上下文了。這就引出了所謂“尾遞歸優化”的概念：
When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.
https://www.oreilly.com/library/view/mastering-algorithms-with/1565924533/ch03s02.html上述文字大意如下：
當(C語言)編譯器檢測到尾遞歸調用時，并不會建立新的棧幀并壓入棧中，而是用新的棧幀覆寫掉目前處于激活狀态的棧幀。編譯器之是以能夠這樣做，是因為尾遞歸函數裡，遞歸調用是目前棧幀裡最後一個需要執行的函數調用。被覆寫掉的棧幀本身毫無用處，不需要再保留。采用棧幀覆寫，而不是建立棧幀的方式，極大程度上減少了棧幀的個數，提高了遞歸函數的執行性能。是以，應該盡可能地去嘗試使用尾遞歸方式實作遞歸函數。
一個實際的性能比較例子：計算20的階乘，二者的性能有巨大差異：普通遞歸實作需要10毫秒，而尾遞歸實作僅僅需要不到1毫秒的時間。
注意：一個遞歸函數能否用尾遞歸方式實作，和它能否享受運作時的尾遞歸優化，二者不是一回事，後者需要編譯器的支援。
應用開發人員通過Scala提供的@tailrec注解，告訴編譯器，對注解修飾的方法進行尾遞歸優化：
如果優化失敗，或者被修飾的方法根本就不是一個尾遞歸函數，則編譯器報錯：
至于ABAP編譯器能否支援尾遞歸優化？我沒有研究過，我隻是覺得，尾遞歸優化并不能算是ABAP編譯器必須實作的需求之一。
希望本文能幫助大家對尾遞歸優化這個概念有一個最基本的認識，感謝閱讀。