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

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

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

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

前段裝箱案例中箱子間的邊長關係,其實是每個程式人都接觸過的費式數列(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所言「過早最佳化是萬惡根源」,正是這樣的道理。

作者簡介


Advertisement

更多 iThome相關內容