遞迴的美麗與哀愁

在數學上，遞迴關係式是指定義序列的方程式中，序列下一項是基於序列一或多個前項計算而來，不少看似複雜的關係，可能是由簡單的遞迴關係式而構成。

在電腦科學中，遞迴的本質是重複地將問題分解為相同子問題的方式，在程式語言支援下，可透過函式中呼叫自身函式來實現遞迴。在運用程式設計解決問題的手法中，遞迴是最基本、簡單，但又最常遭到誤解、忽略的方式。

化繁為簡的遞迴之美
是否曾有這種經驗？打開大箱子取出當中零件或箱子後，卻怎麼也沒辦法把那些零件或箱子剛好地放回大箱子。仔細觀察小零件與次大零件間的關係，或許可找出一些規律，也許湊巧地，小箱子都是正方形，兩個小箱與一個略大箱子組成長方形，而長方形長邊又等於再大一號箱子邊長，這些箱子組成的長方形長邊，又等於更大一號箱子的邊長，如此遞迴下去。

是否觀察過一些複雜圖騰、工程或自然界結構？像是螺殼剖面、葉片生長、雪花或水結晶放大圖等，仔細觀察其中小結構與較大結構間的關係，是否可察覺某種規律性？不少複雜結構，若規律中有遞迴特性，往往發現小結構與大結構間非常單純。

前段裝箱案例中箱子間的邊長關係，其實是每個程式人都接觸過的費式數列（Fibonacci series），如果以箱子邊長為半徑、畫四分之一圓，最後連接起來的弧，會像是螺殼剖面，長久歲月下，自然界許多複雜現象呈現遞迴關係，身邊各個領域也常運用遞迴來解決複雜的需求。

有了遞迴關係，就可以將複雜問題分解為單純子問題，在電腦科學上也運用此概念，為不少問題建立了簡單又有效率的解決方案，像是快速排序法基本概念，就是在數列中選擇一個元素，其餘元素分割為大於該元素與小於該元素的兩個子數列，再分別對兩個子數列進行相同動作；電腦圖學或遊戲中經常運用遞迴，來打造複雜材質或場景，避免在軟體中儲存龐大素材。JS1K（js1k.com）自2010年來舉辦的專題競賽，條件限制了作品，必須是小於1024位元組的JavaScript程式，不少作品就以遞迴概念來呈現複雜視覺效果。

多數程式人從第一門程式語言的學習開始，就必然接觸過遞迴函式，然而多數對遞迴函式有所誤解而印象不佳，認為遞迴具複雜特性且可讀性差，因而存在「遞迴只應天上有，凡人應當用迴圈」這樣的調侃語句；另一方面，由於函式呼叫實際上必須在電腦上運行，會有運算與呼叫堆疊（Call stack）的資源消耗問題，不少人一開始面對問題時，就為了效能問題而避免使用遞迴。

遞迴本質上是將複雜問題單純化，理應不會有複雜而且可讀性差的誤解。會有複雜印象的程式人，往往是因為僅觀察與分解出幾個表層子問題，將之實作為遞迴函式時，會因為這些子問題實際上還包括數個子問題，而在函式中會實作解決多個子問題的演算流程，同時進行多件事情，表示在下層遞迴時，得記得先前各自的狀態，在層層遞迴下，因記憶多層狀態而感到困難重重，你可能得追蹤各層遞迴的多個變數，也可能在每次遞迴中包括了迴圈處理，這讓演算變得複雜，因而也降低了可讀性。

實際上，若變數值是來自某個程式區塊運算後的結果，這表示該程式區塊可以獨立為一個子問題而實作為子函式，區塊執行前的變數值會是子函式的引數，而傳回值就是區塊執行後的變數值，當問題切割為適當子問題，就可以專注實作正確子函式，免於追蹤變數的負擔，可讀性就會提昇。

至於迴圈，本質上就是在處理具重複性的問題，這暗示著它也是可切割出來遞迴的子問題，如果你不能輕易地將迴圈改為遞迴，往往意謂著迴圈中處理了多個子問題，這也是不少人以效能作為藉口，拒絕使用遞迴的原因，因而經常造成迴圈中複雜的演算流程，以及冗長的迴圈區塊，以可讀性作為代價，換取對系統也許無顯著助益的效能。

由於對遞迴的誤解與避免使用，許多人因而更依賴迴圈來思考重複性問題如何解決，面對遞迴時反而覺得不夠直覺，這純綷是被迴圈制約，實際上就處理子問題上兩者等價。

以加總數列為例，迴圈解法將元素elem+sum，結果再指定給sum，實際上sum就是子數列總和，每次迴圈本體是將「元素elem加上子數列總和」；改為遞迴函式sum時，若子數列為subList，函式本體就是elem+sum(subList)，同樣是將「元素elem加上子數列總和」，並無異處，實際上還少了追蹤變數的負擔，在適當語法或API封裝下，還能增加可讀性。

效能的迷思？

無論如何，跑一次迴圈從數列中得到兩個結果，一定比跑兩次迴圈從數列中，分別得到一個結果快吧？

就微觀流程來說，這確實是個誘惑，引誘程式人在迴圈中順便執行其他的工作，增加了理解迴圈中演算的困難度；然而就系統來說，效能是個整體概念，需實際測試多跑一次迴圈，到底額外佔據整體回應中多少時間比，才能知道調整的必要性。

如果真的要調整微觀流程，從資料結構、演算法或平行化的方向設計，就效能上，也往往比單純減少迴圈執行次數來得有幫助。遞迴呼叫在電腦上會產生呼叫堆疊，在有限硬體資源下會有堆疊次數限制，以Java為例，如果超過堆疊次數，就會拋出StackOverflowError，這可考慮在系統可接受情況下，調整執行環境參數來增加堆疊次數，或者考慮將遞迴調整為尾端遞迴（Tail recursion）、使用Trampoline，或是直接拆解為迴圈。

尾端遞迴是指每次遞迴呼叫自身函式的結果，亦被直接傳回。有些程式語言會針對尾端遞迴進行調整，例如Scala編譯器會將直接尾端遞迴（Direct tail recursion）消去而成為迴圈，然而，尾端遞迴消去（Tail recursion elimination）或甚至更進一步的尾端呼叫消去（Tail call optimization）並非每個語言都支援，這牽涉到語法本身是否容許以及語言風格。

就後者而言，由於遞迴被消去而成為迴圈，有時會造成除錯困惑，Python創建者Guido van Rossum不贊成尾端遞迴消去，簡單的理由是「It's simply unpythonic.」，也就是這不符合Python慣用法。

在不支援尾端遞迴消去的語言中，可運用Trampoline概念，將直接呼叫函式的堆疊結構，改為間接呼叫函式的線性結構。在支援一級函式的語言中，可簡單地使用函式物件，將尾端遞迴呼叫封裝並傳回，如此就可使用迴圈反覆呼叫函式物件，直到結果傳回；在不支援一級函式的語言中，像是Java，可以使用Functor來實現。

如果以上方式都不合用，在遞迴函式職責夠單純下，也可輕易拆解為迴圈，也可進一步從資料結構、演算法或平行化的方向設計，畢竟過深的遞迴即使改為迴圈，也代表該迴圈會執行許久，也許解題方式有重新設計的必要。

效能改進方式常在良好可讀性下呈現
可讀性與效能幾乎總是對立的，無論是尾端遞迴、使用Trampoline、拆解成迴圈或是重新設計演算法，或多或少都會增加原有程式的複雜度，降低程式可讀性。

然而正因為效能與可讀性幾乎總是對立，更應該在一開始優先考慮可讀性，盡量將問題分解為子問題，後續若確認系統中某個環節出現效能問題，在良好可讀性下，也容易呈現效能改進方式。若一開始就考慮效能而犧牲了可讀性，在一片混亂的程式碼中，要再改進效能反而會困難重重，Donald Ervin Knuth所言「過早最佳化是萬惡根源」，正是這樣的道理。