iThome 網站首載：遞迴的美麗與哀愁
在數學上，遞迴關係式是指定義序列的方程式中，序列下一項是基於序列一或多個前項計算而來，不少看似複雜的關係，可能是由簡單的遞迴關係式而構成。在電腦科學中，遞迴的本質是重複地將問題分解為相同子問題的方式，在程式語言支援下，可透過函式中呼叫自身函式來實現遞迴。在運用程式設計解決問題的手法中，遞迴是最基本、簡單但又最常遭到誤解、忽略的方式。
- 化繁為簡的遞迴之美
是否曾有這種經驗？打開大箱子取出當中零件或箱子後，卻怎麼也沒辦法把那些零件或箱子剛好地放回大箱子。仔細觀察小零件與次大零件間的關係，或許可找出一些規律，也許湊巧地，小箱子都是正方形，兩個小箱與一個略大箱子組成長方形，而長方形長邊又等於再大一號箱子邊長，這些箱子組成的長方形長邊又等於更大一號箱子的邊長，如此遞迴下去。
是否觀察過一些複雜圖騰、工程或自然界結構？像是螺殼剖面、葉片生長、雪花或水結晶放大圖等，仔細觀察其中小結構與較大結構間的關係，是否可察覺某種規律性？不少複雜結構，若規律中有遞迴特性，往往發現小結構與大結構間非常單純。前段裝箱案例中箱子間的邊長關係，其實是每個程式人都接觸過的費式數列（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所言「過早最佳化是萬惡根源」，正是這樣的道理。