本章內容
為什麼要進行函數式編程
什麼是函數式編程
聲明式編程以及引用透明性
編寫函數式Java的準則
迭代和遞歸
你已經發現了，本書中頻繁地出現“函數式”這個術語。到目前為止，你可能也對函數式編程包含哪些內容有了一定的瞭解。它指的是Lambda表達式和一等函數嗎？還是說限制你對可變對象的修改？如果是這樣，採用函數式編程能為你帶來什麼好處呢？這一章中，我們會一一為你解答這些問題。我們會介紹什麼是函數式編程，以及它的一些術語。我們首先會探究函數式編程背後的概念，比如副作用、不變性、聲明式編程、引用透明性，並將它們和Java 8的實踐相結合。下一章，我們會更深入地研究函數式編程的技術，包括高階函數、科裡化、持久化數據結構、延遲列表、模式匹配以及結合器。
13.1 實現和維護系統
讓我們假設你被要求對一個大型的遺留軟件系統進行升級，而且這個系統你之前並不是非常瞭解。你是否應該接受維護這種軟件系統的工作呢？稍有理智的外包Java程序員只會依賴如下這種言不由衷的格言做決定，“搜索一下代碼中有沒有使用synchronized關鍵字，如果有就直接拒絕（由此我們可以瞭解修復並發導致的缺陷有多困難），否則進一步看看系統結構的複雜程度”。我們會在下面中提供更多的細節，但是你發現了嗎，正如我們在前面幾章所討論的，如果你喜歡無狀態的行為（即你處理Stream的流水線中的函數不會由於需要等待從另一個方法中讀取變量，或者由於需要寫入的變量同時有另一個方法正在寫而發生中斷），Java 8中新增的Stream提供了強大的技術支撐，讓我們無需擔心鎖引起的各種問題，充分發掘系統的並發能力。
為了讓程序易於使用，你還希望它具備哪些特性呢？你會希望它具有良好的結構，最好類的結構應該反映出系統的結構，這樣能便於大家理解；甚至軟件工程中還提供了指標，對結構的合理性進行評估，比如耦合性（軟件系統中各組件之間是否相互獨立）以及內聚性（系統的各相關部分之間如何協作）。
不過，對大多數程序員而言，最關心的日常要務是代碼維護時的調試：代碼遭遇一些無法預期的值就有可能發生崩潰。為什麼會發生這種情況？它是如何進入到這種狀態的？想想看你有多少代碼維護的顧慮都能歸咎到這一類！1很明顯，函數式編程提出的“無副作用”以及“不變性”對於解決這一難題是大有裨益的。讓我們就此展開進一步的探討。
1推薦你閱讀Michael Feathers的Working Effectively with Legacy Code 詳細瞭解這個話題。
13.1.1 共享的可變數據
最終，我們剛才討論的無法預知的變量修改問題，都源於共享的數據結構被你所維護的代碼中的多個方法讀取和更新。假設幾個類同時都保存了指向某個列表的引用。那麼到底誰對這個列表擁有所屬權呢？如果一個類對它進行了修改，會發生什麼情況？其他的類預期會發生這種變化嗎？其他的類又如何得知列表發生了修改呢？我們需要通知使用該列表的所有類這一變化嗎？抑或是不是每個類都應該為自己準備一份防禦式的數據備份以備不時之需呢？換句話說，由於使用了可變的共享數據結構，我們很難追蹤你程序的各個組成部分所發生的變化。圖13-1解釋了這一問題。
圖 13-1 多個類同時共享的一個可變對象。我們很難說到底哪個類真正擁有該對像
假設有這樣一個系統，它不修改任何數據。維護這樣的一個系統將是一個無以倫比的美夢，因為你不再會收到任何由於某些對像在某些地方修改了某個數據結構而導致的意外報告。如果一個方法既不修改它內嵌類的狀態，也不修改其他對象的狀態，使用return返回所有的計算結果，那麼我們稱其為純粹的或者無副作用的。
更確切地講，到底哪些因素會造成副作用呢？簡而言之，副作用就是函數的效果已經超出了函數自身的範疇。下面是一些例子。
-
除了構造器內的初始化操作，對類中數據結構的任何修改，包括字段的賦值操作（一個典型的例子是
setter方法）。 -
拋出一個異常。
-
進行輸入/輸出操作，比如向一個文件寫數據。
從另一個角度來看“無副作用”的話，我們就應該考慮不可變對象。不可變對象是這樣一種對象，它們一旦完成初始化就不會被任何方法修改狀態。這意味著一旦一個不可變對像初始化完畢，它永遠不會進入到一個無法預期的狀態。你可以放心地共享它，無需保留任何副本，並且由於它們不會被修改，還是線程安全的。
“無副作用”這個想法的限制看起來很嚴苛，你甚至可能會質疑是否有真正的生產系統能夠以這種方式構建。我們希望結束本章的學習之後，你能夠確信這一點。一個好消息是，如果構成系統的各個組件都能遵守這一原則，該系統就能在完全無鎖的情況下，使用多核的並發機制，因為任何一個方法都不會對其他的方法造成干擾。此外，這還是一個讓你瞭解你的程序中哪些部分是相互獨立的非常棒的機會。
這些思想都源於函數式編程，我們在下一節會進行介紹。但是在開始之前，讓我們先看看函數式編程的基石聲明式編程吧。
13.1.2 聲明式編程
一般通過編程實現一個系統，有兩種思考方式。一種專注於如何實現，比如：“首先做這個，緊接著更新那個，然後……”舉個例子，如果你希望通過計算找出列表中最昂貴的事務，通常需要執行一系列的命令：從列表中取出一個事務，將其與臨時最昂貴事務進行比較；如果該事務開銷更大，就將臨時最昂貴的事務設置為該事務；接著從列表中取出下一個事務，並重複上述操作。
這種“如何做”風格的編程非常適合經典的面向對像編程，有些時候我們也稱之為“命令式”編程，因為它的特點是它的指令和計算機底層的詞彙非常相近，比如賦值、條件分支以及循環，就像下面這段代碼：
Transaction mostExpensive = transactions.get(0);
if(mostExpensive == null)
throw new IllegalArgumentException("Empty list of transactions")
for(Transaction t: transactions.subList(1, transactions.size)){
if(t.getValue > mostExpensive.getValue){
mostExpensive = t;
}
}
另一種方式則更加關注要做什麼。你在第4章和第5章中已經看到，使用Stream API你可以指定下面這樣的查詢：
Optional<Transaction> mostExpensive =
transactions.stream
.max(comparing(Transaction::getValue));
這個查詢把最終如何實現的細節留給了函數庫。我們把這種思想稱之為內部迭代。它的巨大優勢在於你的查詢語句現在讀起來就像是問題陳述，由於採用了這種方式，我們馬上就能理解它的功能，比理解一系列的命令要簡潔得多。
採用這種“要做什麼”風格的編程通常被稱為聲明式編程。你制定規則，給出了希望實現的目標，讓系統來決定如何實現這個目標。它帶來的好處非常明顯，用這種方式編寫的代碼更加接近問題陳述了。
13.1.3 為什麼要採用函數式編程
函數式編程具體實踐了前面介紹的聲明式編程（“你只需要使用不相互影響的表達式，描述想要做什麼，由系統來選擇如何實現”）和無副作用計算。正如我們前面所討論的，這兩個思想能幫助你更容易地構建和維護系統。
同時也請注意，我們在第3章中使用Lambda表達式介紹的內容，即一些語言的特性，比如構造操作和傳遞行為對於以自然的方式實現聲明式編程是必要的，它們能讓我們的程序更便於閱讀，易於編寫。你可以使用Stream將幾個操作串接在一起，表達一個複雜的查詢。這些都是函數式編程語言的特性；我們在14.5節中介紹結合器時會更加深入地介紹這些內容。
為了讓你有更直觀的感受，我們會結合Java 8介紹這些語言的新特性，現在我們會具體給出函數式編程的定義，以及它在Java語言中的表述。我們希望表達的是，使用函數式編程，你可以實現更加健壯的程序，還不會有任何的副作用。
13.2 什麼是函數式編程
對於“什麼是函數式編程”這一問題最簡化的回答是“它是一種使用函數進行編程的方式”。那什麼是函數呢？
我們很容易想像這樣一個方法，它接受一個整型和一個浮點型參數，返回一個浮點型的結果——它也有副作用，隨著調用次數的增加，它會不斷地更新共享變量，如圖13-2所示。
圖 13-2 帶有副作用的函數
在函數式編程的上下文中，一個“函數”對應於一個數學函數：它接受零個或多個參數，生成一個或多個結果，並且不會有任何副作用。你可以把它看成一個黑盒，它接收輸入並產生一些輸出，如圖13-3所示。
圖 13-3 一個沒有任何副作用的函數
這種類型的函數和你在Java編程語言中見到的函數之間的區別是非常重要的（我們無法想像，log或者 sin這樣的數學函數會有副作用）。尤其是，使用同樣的參數調用數學函數，它所返回的結果一定是相同的。這裡，我們暫時不考慮Random.nextInt這樣的方法，稍後我們會在介紹引用透明性時討論這部分內容。
當談論“函數式”時，我們想說的其實是“像數學函數那樣——沒有副作用”。由此，編程上的一些精妙問題隨之而來。我們的意思是，每個函數都只能使用函數和像if-then-else這樣的數學思想來構建嗎？或者，我們也允許函數內部執行一些非函數式的操作，只要這些操作的結果不會暴露給系統中的其他部分？換句話說，如果程序有一定的副作用，不過該副作用不會為其他的調用者感知，是否我們能假設這種副作用不存在呢？調用者不需要知道，或者完全不在意這些副作用，因為這對它完全沒有影響。
當我們希望能界定這二者之間的區別時，我們將第一種稱為純粹的函數式編程（在本章的最後會討論這部分內容），後者稱為函數式編程。
13.2.1 函數式Java編程
編程實戰中，你是無法用Java語言以純粹的函數式來完成一個程序的。比如，Java的I/O模型就包含了帶副作用的方法（調用Scanner.nextLine就有副作用，它會從一個文件中讀取一行，通常情況兩次調用的結果完全不同）。不過，你還是有可能為你系統的核心組件編寫接近純粹函數式的實現。在Java語言中，如果你希望編寫函數式的程序，首先需要做的是確保沒有人能覺察到你代碼的副作用，這也是函數式的含義。假設這樣一個函數或者方法，它沒有副作用，進入方法體執行時會對一個字段的值加一，退出方法體之前會對該字段減一。對一個單線程的程序而言，這個方法是沒有副作用的，可以看作函數式的實現。換個角度而言，如果另一個線程可以查看該字段的值——或者更糟糕的情況，該方法會同時被多個線程並發調用——那麼這個方法就不能稱之為函數式的實現了。當然，你可以用加鎖的方式對方法的方法體進行封裝，掩蓋這一問題，你甚至可以再次聲稱該方法符合函數式的約定。但是，這樣做之後，你就失去了在你的多核處理器的兩個核上並發執行兩個方法調用的能力。它的副作用對程序可能是不可見的，不過對於程序員你而言是可見的，因為程序運行的速度變慢了！
我們的準則是，被稱為“函數式”的函數或方法都只能修改本地變量。除此之外，它引用的對象都應該是不可修改的對象。通過這種規定，我們期望所有的字段都為final類型，所有的引用類型字段都指向不可變對象。後續的內容中，你會看到我們實際也允許對方法中全新創建的對象中的字段進行更新，不過這些字段對於其他對象都是不可見的，也不會因為保存對後續調用結果造成影響。
我們前述的準則是不完備的，要成為真正的函數式程序還有一個附加條件，不過它在最初時不太為大家所重視。要被稱為函數式，函數或者方法不應該拋出任何異常。關於這一點，有一個極為簡單而又極為教條的解釋：你不應該拋出異常，因為一旦拋出異常，就意味著結果被終止了；不再像我們之前討論的黑盒模式那樣，由return返回一個恰當的結果值。不過，這一規則似乎又和我們實際的數學使用有衝突：雖然合法的數學函數為每個合法的參數值返回一個確定的結果，很多通用的數學操作在嚴格意義上稱之為局部函數式（partial function）可能更為妥當。這種函數對於某些輸入值，甚至是大多數的輸入值都返回一個確定的結果；不過對另一些輸入值，它的結果是 未定義的，甚至不返回任何結果。這其中一個典型的例子是除法和開平方運算，如果除法的第二操作數是0，或者開平方的參數為負數就會發生這樣的情況。以Java那樣拋出一個異常的方式對這些情況進行建模看起來非常自然。這裡存在著一定的爭執，有的作者認為拋出代表嚴重錯誤的異常是可以接受的，但是捕獲異常是一種非函數式的控制流，因為這種操作違背了我們在黑盒模型中定義的“傳遞參數，返回結果”的規則，引出了代表異常處理的第三支箭頭，如圖13-4所示。
圖 13-4 拋出一個異常的方法
那麼，如果不使用異常，你該如何對除法這樣的函數進行建模呢？答案是請使用Optional<T>類型：你應該避免讓sqrt使用double sqrt(double)這樣的函數簽名，因為這種方式可能拋出異常；與之相反我們推薦你使用Optional<Double> sqrt(double)——這種方式下，函數要麼返回一個值表示調用成功，要麼返回一個對象，表明其無法進行指定的操作。當然，這意味著調用者需要檢查方法返回的是否為一個空的Optional對象。這件事聽起來代價不小，依據我們之前對函數式編程和純粹的函數式編程的比較，從實際操作的角度出發，你可以選擇在本地局部地使用異常，避免通過接口將結果暴露給其他方法，這種方式既取得了函數式的優點，又不會過度膨脹代碼。
最後，作為函數式的程序，你的函數或方法調用的庫函數如果有副作用，你必須設法隱藏它們的非函數式行為，否則就不能調用這些方法（換句話說，你需要確保它們對數據結構的任何修改對於調用者都是不可見的，你可以通過首次複製，或者捕獲任何可能拋出的異常實現這一目的）。在13.2.4節中，你會看到這樣的例子，我們通過複製列表的方式，有效地隱藏了方法insertAll調用庫函數List.add所產生的副作用。
這些方法通常會使用註釋或者使用標記註釋聲明的方式進行標注——符合我們規定的函數，我們可以將其作為參數傳遞給並發流處理操作，比如我們在第4~7章介紹過的Stream.map方法。
為了各種各樣的實戰需求，你最終可能會發現即便對函數式的代碼，我們還是需要向某些日誌文件打印輸出調試信息。是的，這意味著嚴格意義上說，這些代碼並非函數式的，但是你已經在實際中享受了函數式程序帶來的大多數好處。
13.2.2 引用透明性
“沒有可感知的副作用”（不改變對調用者可見的變量、不進行I/O、不拋出異常）的這些限制都隱含著引用透明性。如果一個函數只要傳遞同樣的參數值，總是返回同樣的結果，那這個函數就是引用透明的。String.replace方法就是引用透明的，因為像"raoul".replace('r', 'R')這樣的調用總是返回同樣的結果（replace方法返回一個新的字符串，用小寫的r替換掉所有大寫的R），而不是更新它的this對象，所以它可以被看成函數式的。
換句話說，函數無論在何處、何時調用，如果使用同樣的輸入總能持續地得到相同的結果，就具備了函數式的特徵。這也解釋了我們為什麼不把Random.nextInt看成函數式的方法。Java語言中，使用Scanner對像從用戶的鍵盤讀取輸入也違反了引用透明性原則，因為每次調用nextLine時都可能得到不同的結果。不過，將兩個final int類型的變量相加總能得到同樣的結果，因為在這種聲明方式下，變量的內容是不會被改變的。
引用透明性是理解程序的一個重要屬性。它還包含了對代價昂貴或者需長時間計算才能得到結果的變量值的優化（通過保存機制而不是重複計算），我們通常將其稱為記憶化或者緩存。雖然重要，但是現在討論還是有些跑題，我們會在14.5節進行介紹。
Java語言中，關於引用透明性還有一個比較複雜的問題。假設你對一個返回列表的方法調用了兩次。這兩次調用會返回內存中的兩個不同列表，不過它們包含了相同的元素。如果這些列表被當作可變的對象值（因此是不相同的），那麼該方法就不是引用透明的。如果你計劃將這些列表作為單純的值（不可修改），那麼把這些值看成相同的是合理的，這種情況下該方法是引用透明的。通常情況下，在函數式編程中，你應該選擇使用引用透明的函數。我們會在14.5節繼續討論這一主題。現在我們想探討從更大的範圍看是否應該修改對象的值。
13.2.3 面向對象的編程和函數式編程的對比
我們由函數式編程和（極端）典型的面向對像編程的對比入手進行介紹，最終你會發現Java 8認為這些風格其實只是面向對象的一個極端。作為Java程序員，毫無疑問，你一定使用過某種函數式編程，也一定使用過某些我們稱為極端面向對象的編程。正如我們在第1章中所介紹的那樣，由於硬件（比如多核）和程序員期望（比如使用類數據庫查詢式的語言去操縱數據）的變化，促使Java的軟件工程風格在某種程度上愈來愈向函數式的方向傾斜，本書的目的之一就是要幫助你應對這種潮流的變化。
關於這個問題有兩種觀點。一種支持極端的面向對像：任何事物都是對象，程序要麼通過更新字段完成操作，要麼調用對與它相關的對象進行更新的方法。另一種觀點支持引用透明的函數式編程，認為方法不應該有（對外部可見的）對像修改。實際操作中，Java程序員經常混用這些風格。你可能會使用包含了可變內部狀態的迭代器遍歷某個數據結構，同時又通過函數式的方式（我們曾經討論過，可以使用可變局部變量實現這一目標）計算數據結構中的變量之和。本章接下來的一節以及下一章中主要的內容都圍繞這函數式編程的技巧展開，幫助你編寫更加模塊化，更適應多核處理器的應用程序。這些技巧和思想會成為你編程武器庫中的秘密武器。
13.2.4 函數式編程實戰
讓我們從解決一個示例函數式的編程練習題入手：給定一個列表List<value>，比如{1, 4, 9}，構造一個List<List<Integer>>，它的成員都是類表{1, 4, 9}的子集——我們暫時不考慮元素的順序。{1, 4, 9}的子集是{1, 4, 9}、{1, 4}、{1, 9}、{4, 9}、{1}、{4}、{9}以及{}。
包括空子集在內，這樣的子集總共有8個。每個子集都使用List<Integer>表示，這就是答案中期望的List<List<Integer>>類型。
通常新手碰到這個問題都會覺得無從下手，對於“{1, 4, 9}的子集可以劃分為包含1和不包含 1的兩部分”也需要特別解釋2。不包含1的子集很簡單就是{4, 9}，包含1的子集可以通過將1插入到{4, 9}的各子集得到。這樣我們就能利用Java，以一種簡單、自然、自頂向下的函數式編程方式實現該程序了（一個常見的編程錯誤是認為空的列表沒有子集）。
2偶爾會有些麻煩（機智！）的學生指出另一種解法，這是一種純粹的代碼把戲，它利用二進制來表示數字（Java解決方案的代碼分別對應於000,001,010,011,100,101,110,111）。我們告訴這些學生要通過計算得出結果，而不是通過列出所有列表的排列組合；比如以{1,4,9}而言，它就有六種排列組合。
static List<List<Integer>> subsets(List<Integer> list) {
if (list.isEmpty) { ←─如果輸入為空，它就只包含一個子集，既空列表自身
List<List<Integer>> ans = new ArrayList<>;
ans.add(Collections.emptyList);
return ans;
}
Integer first = list.get(0);
List<Integer> rest = list.subList(1,list.size);
List<List<Integer>> subans = subsets(rest); ←─否則就取出一個元素first，找出剩餘部分的所有子集，並將其賦予subans。subans構成了結果的另外一半
List<List<Integer>> subans2 = insertAll(first, subans); ←─答案的另一半是subans2 ， 它包含了subans中的所有列表，但是經過調整，在每個列表的第一個元素之前添加了first
return concat(subans, subans2); ←─將兩個子答案整合在一起就完成了任務，簡單嗎？
}
如果給出的輸入是{1, 4, 9}，程序最終給出的答案是{{}, {9}, {4}, {4, 9}, {1}, {1, 9}, {1, 4}, {1, 4, 9}}。當你完成了缺失的兩個方法之後可以實際運行下這個程序。
我們一起回顧下你已經完成了哪些工作。你假設缺失的方法insertAll和concat自身都是函數式的，並依此推斷你的subsets方法也是函數式的，因為該方法中沒有任何操作會修改現有的結構（如果你熟悉數學的話，你大概對此很熟悉，這就是著名的歸納法啊）。
現在，讓我們看看如何定義insertAll方法。這是第一個可能出現的坑。假設你已經定義好了insertAll，它會修改傳遞給它的參數。那麼，該程序會以修改subans2同樣的方式，錯誤地修改subans，最終導致答案中莫名地包含了{1, 4, 9}的8個副本。與之相反，你可以像下面這樣實現insertAll的功能：
static List<List<Integer>> insertAll(Integer first,
List<List<Integer>> lists) {
List<List<Integer>> result = new ArrayList<>;
for (List<Integer> list : lists) {
List<Integer> copyList = new ArrayList<>; ←─複製列表，從而使你有機會對其進行添加操作。即使底層是可變的，你也不應該複製底層的結構（不過Integer底層是不可變的）
copyList.add(first);
copyList.addAll(list);
result.add(copyList);
}
return result;
}
注意到了嗎？你現在已經創建了一個新的List，它包含了subans的所有元素。你聰明地利用了Integer對像無法修改這一優勢，否則你需要為每個元素創建一個副本。由於聚焦於讓insertAll像函數式那樣地工作，你很自然地將所有的複製操作放到了insertAll中，而不是它的調用者中。
最終，你還需要定義concat方法。這個例子中，我們提供了一個簡單的實現，但是我們希望你不要這樣使用（我們展示這段代碼的目的只是為了便於你比較不同的編程風格）。
static List<List<Integer>> concat(List<List<Integer>> a,
List<List<Integer>> b) {
a.addAll(b);
return a;
}
不過，我們真正建議你採用的是下面這種方式：
static List<List<Integer>> concat(List<List<Integer>> a,
List<List<Integer>> b) {
List<List<Integer>> r = new ArrayList<>(a);
r.addAll(b);
return r;
}
為什麼呢？第二個版本的concat是純粹的函數式。雖然它在內部會對對像進行修改（向列表r添加元素），但是它返回的結果基於參數卻沒有修改任何一個傳入的參數。與此相反，第一個版本基於這樣的事實，執行完concat(subans, subans2)方法調用後，沒人需要再次使用subans的值。對於我們定義的subsets，這的確是事實，所以使用簡化版本的concat是個不錯的選擇。不過，這也取決於你如何審視你的時間，你是願意為定位詭異的缺陷費勁心機耗費時間呢？還是花費些許的代價創建一個對象的副本呢？
無論你怎樣解釋這個不太純粹的concat方法，“只會用於第一參數可以被強制覆蓋的場景，或者只會使用在這個subsets方法中，任何對subsets的修改都會遵照這一標準進行代碼評審”，一旦將來的某一天，某個人發現這段代碼的某些部分可以復用，並且似乎可以工作時，你未來調試的夢魘就開始了。我們會在14.2節繼續討論這一問題。
請牢記：考慮編程問題時，採用函數式的方法，關注函數的輸入參數以及輸出結果（即你希望做什麼），通常比設計階段的早期就考慮如何做、修改哪些東西要卓有成效得多。我們現在轉入介紹更深入的遞歸，它是函數式編程特別推崇的一種技術，能幫你更深刻地理解“做什麼”這一風格。
13.3 遞歸和迭代
純粹的函數式編程語言通常不包含像while或者for這樣的迭代構造器。為什麼呢？因為這種類型的構造器經常隱藏著陷阱，誘使你修改對象。比如，while循環中，循環的條件需要更新；否則循環就一次都不會執行，要麼就進入無限循環的狀態。但是，很多情況下循環還是非常有用的。我們在前面的介紹中已經聲明過，如果沒有人能感知的話，函數式也允許進行變更，這意味著我們可以修改局部變量。我們在Java中使用的for-each循環，for(Apple a : apples { }如果用迭代器方式重寫，代碼如下：
Iterator<Apple> it = apples.iterator;
while (it.hasNext) {
Apple apple = it.next;
// ...
}
這並不是問題，因為改變發生時，這些變化（包括使用next方法對迭代器狀態的改變以及在while循環內部對apple變量的賦值）對於方法的調用方是不可見的。但是，如果使用 for-each循環，比如像下面這個搜索算法就會帶來問題，因為循環體會對調用方共享的數據結構進行修改：
public void searchForGold(List<String> l, Stats stats){
for(String s: l){
if("gold".equals(s)){
stats.incrementFor("gold");
}
}
}
實際上，對函數式而言，循環體帶有一個無法避免的副作用：它會修改stats對象的狀態，而這和程序的其他部分是共享的。
由於這個原因，純函數式編程語言，比如Haskell直接去除了這樣的帶有副作用的操作！之後你該如何編寫程序呢？比較理論的答案是每個程序都能使用無需修改的遞歸重寫，通過這種方式避免使用迭代。使用遞歸，你可以消除每步都需更新的迭代變量。一個經典的教學問題是用迭代的方式或者遞歸的方式（假設輸入值大於1）編寫一個計算階乘的函數（參數為正數），代碼列表如下。
代碼清單13-1 迭代式的階乘計算
static int factorialIterative(int n) {
int r = 1;
for (int i = 1; i <= n; i++) {
r *= i;
}
return r;
}
代碼清單13-2 遞歸式的階乘計算
static long factorialRecursive(long n) {
return n == 1 ? 1 : n * factorialRecursive(n-1);
}
第一段代碼展示了標準的基於循環的結構：變量r和i在每輪循環中都會被更新。第二段代碼以更加類數學的形式給出一個遞歸方法（方法調用自身）的實現。Java語言中，使用遞歸的形式通常效率都更差一些，我們很快會討論這方面的內容。
但是，如果你已經仔細閱讀過本書的前面章節，一定知道Java 8的Stream提供了一種更加簡單的方式，用描述式的方法來定義階乘，代碼如下。
代碼清單13-3 基於Stream的階乘
static long factorialStreams(long n){
return LongStream.rangeClosed(1, n)
.reduce(1, (long a, long b) -> a * b);
}
現在，我們回來談談效率問題。作為Java的用戶，相信你已經意識到函數式程序的狂熱支持者們總是會告訴你說，應該使用遞歸，摒棄迭代。然而，通常而言，執行一次遞歸式方法調用的開銷要比迭代執行單一機器級的分支指令大不少。為什麼呢？每次執行factorialRecursive方法調用都會在調用棧上創建一個新的棧幀，用於保存每個方法調用的狀態（即它需要進行的乘法運算），這個操作會一直指導程序運行直到結束。這意味著你的遞歸迭代方法會依據它接收的輸入成比例地消耗內存。這也是為什麼如果你使用一個大型輸入執行factorialRecursive方法，很容易遭遇StackOverflowError異常：
Exception in thread "main" java.lang.StackOverflowError
這是否意味著遞歸百無一用呢？當然不是！函數式語言提供了一種方法解決這一問題：尾-調優化（tail-call optimization）。基本的思想是你可以編寫階乘的一個迭代定義，不過迭代調用發生在函數的最後（所以我們說調用發生在尾部）。這種新型的迭代調用經過優化後執行的速度快很多。作為示例，下面是一個階乘的“尾-遞”（tail-recursive）定義。
代碼清單13-4 基於“尾-遞”的階乘
static long factorialTailRecursive(long n) {
return factorialHelper(1, n);
}
static long factorialHelper(long acc, long n) {
return n == 1 ? acc : factorialHelper(acc * n, n-1);
}
方法factorialHelper屬於“尾-遞”類型的函數，原因是遞歸調用發生在方法的最後。對比我們前文中factorialRecursive方法的定義，這個方法的最後一個操作是乘以n，從而得到遞歸調用的結果。
這種形式的遞歸是非常有意義的，現在我們不需要在不同的棧幀上保存每次遞歸計算的中間值，編譯器能夠自行決定復用某個棧幀進行計算。實際上，在factorialHelper的定義中，立即數（階乘計算的中間結果）直接作為參數傳遞給了該方法。再也不用為每個遞歸調用分配單獨的棧幀用於跟蹤每次遞歸調用的中間值——通過方法的參數能夠直接訪問這些值。
圖13-5和圖13-6解釋了使用遞歸和“尾-遞”實現階乘定義的不同。
圖 13-5 使用棧楨方式的階乘的遞歸定義
圖 13-6 階乘的尾-遞定義，這裡它只使用了一個棧幀
壞消息是，目前Java還不支持這種優化。但是使用相對於傳統的遞歸，“尾-遞”可能是更好的一種方式，因為它為最終實現編譯器優化開啟了一扇門。很多的現代JVM語言，比如Scala和Groovy都已經支持對這種形式的遞歸的優化，最終實現的效果和迭代不相上下（它們的運行速度幾乎是相同的）。這意味著堅持純粹函數式既能享受它的純淨，又不會損失執行的效率。
使用Java 8進行編程時，我們有一個建議，你應該盡量使用Stream取代迭代操作，從而避免變化帶來的影響。此外，如果遞歸能讓你以更精煉，並且不帶任何副作用的方式實現算法，你就應該用遞歸替換迭代。實際上，我們看到使用遞歸實現的例子更加易於閱讀，同時又易於實現和理解（比如，我們在前文中展示的子集的例子），大多數時候編程的效率要比細微的執行時間差異重要得多。
這一節，我們討論了函數式編程，但僅僅是初步介紹了函數式方法的思想——我們介紹的內容甚至適用於最早版本的Java。接下來的一章，我們會討論Java 8攜眷著的一類函數具備了哪些讓人耳目一新的強大能力。
13.4 小結
下面是這一章中你應該掌握的關鍵概念。
-
從長遠看，減少共享的可變數據結構能幫助你降低維護和調試程序的代價。
-
函數式編程支持無副作用的方法和聲明式編程。
-
函數式方法可以由它的輸入參數及輸出結果進行判斷。
-
如果一個函數使用相同的參數值調用，總是返回相同的結果，那麼它是引用透明的。採用遞歸可以取得迭代式的結構，比如
while循環。 -
相對於Java語言中傳統的遞歸，“尾-遞”可能是一種更好的方式，它開啟了一扇門，讓我們有機會最終使用編譯器進行優化。