遞歸是“以一種自相似的方式來重復(fù)事物的過程”，也是向運行時托付操作細(xì)節(jié)的一個例子，而且和函數(shù)式編程有著極為密切的聯(lián)系。以具體的實踐來說，遞歸是以一種帶點計算機科學(xué)味道的方式來對一組事物進行迭代，讓事物的集合反復(fù)對自身調(diào)用同樣的方法，使集合隨著每次迭代不斷縮小，同時要始終小心地保證退出條件的有效性。
問題核心就是對一個不斷變短的列表反復(fù)地做同一件事，把遞歸用在這樣的場合，寫出來的代碼就容易理解。
換個角度看列表
在C或類C語言（包括Java）角度，列表是一個帶索引的集合。
依靠（不一定直接露面的）索引來完成的列表遍歷：
Groovy還提供了eachWithIndex()迭代子，要求傳給它的代碼塊帶有索引參數(shù)，適用于需要顯式訪問索引的場合。
作為“帶索引的格子”的列表形象：
在函數(shù)式語言角度，列表是由列表的第一個元素（叫作頭部）和列表的其余元素（叫作尾部）這兩部分組合而成。
分成頭和尾兩部分的列表形象：
把列表想象成頭部和尾部的組合，有利于使用遞歸的方式來組織迭代：
以遞歸方式進行的列表遍歷：
recurseList()方法首先檢查傳入的列表里還有沒有元素。如果沒有，那就表示迭代工作已經(jīng)完成，可以返回了。如果還有元素，那么用Groovy提供的head()方法取出第一個元素，把它打印出來，然后繼續(xù)對列表的余下部分調(diào)用recurseList()方法。
遞歸方法的缺點
遞歸操作往往受制平臺而存在一些固有的技術(shù)限制，因此這種技法絕非萬靈藥。但對于長度不大的列表來說，遞歸操作是安全的。
從長遠(yuǎn)來看，還是應(yīng)該更多地投入到良好的代碼結(jié)構(gòu)上，技術(shù)限制總會隨著時間減少或者消失化中。遞歸寫法作為一種有缺點的代碼結(jié)構(gòu)，其優(yōu)點并不那么直觀。
命令式和遞歸式的對比
命令式寫法的篩選函數(shù)，Groovy實現(xiàn)：
先創(chuàng)建一個新列表來存放希望保留的元素，然后對原列表進行迭代，讓謂詞判定每個元素的去留，最后返回保留元素的列表。
遞歸式寫法的篩選函數(shù)，Groovy實現(xiàn)：
filter() 函數(shù)首先檢查傳入的列表的大小，若列表中已經(jīng)沒有元素，則返回列表。否則用篩選條件檢查列表的頭部，如果頭部滿足篩選條件，就把它放入列表（代碼中用了一個空列表“[]”作為初始值來保證返回類型是正確的），不然就繼續(xù)遞歸地對列表的尾部篩選下去。
誰來管理狀態(tài)？在命令式的寫法中，是“我”在管理狀態(tài)?！拔摇北仨殑?chuàng)建一個叫new_list的新變量，“我”負(fù)責(zé)向新列表添加元素，“我”負(fù)責(zé)在篩選完成后返回新列表。而在遞歸寫法中，是語言在管理返回值，它從遞歸棧里收集每次方法調(diào)用的返回結(jié)果，構(gòu)造出最終的返回值。遞歸例子中的filter()方法的每一條結(jié)束路徑都返回到遞歸調(diào)用的上一層，隨著棧中的調(diào)用一層一層地返回，各層得到的中間結(jié)果也自動匯集到一起。于是程序員卸下了對new_list的管理責(zé)任，交由語言去替我們照料。
利用遞歸，把狀態(tài)的管理責(zé)任推給運行時。
Scala語言遞歸的實現(xiàn)(還含柯里化)
Scala的列表構(gòu)造運算符“
::”起到了提高代碼可讀性的作用，篩選通過和不通過這兩種情形下返回結(jié)果的變動，表述得清晰易懂。filter()方法遞歸地使用參數(shù)p來篩選一個整數(shù)列表，其中參數(shù)p是一個布爾函數(shù)，或者按照函數(shù)式領(lǐng)域的術(shù)語叫作“謂詞”（predicate）函數(shù)。filter()方法檢查列表是否為空，若是則直接返回；否則用謂詞來檢驗列表的第一個元素（xs.head），判斷是否應(yīng)放入篩選后的列表。
如果頭部滿足謂詞條件，那么就返回以該頭部為首，再加上尾部的篩選結(jié)果組成的新列表。如果頭部通不過謂詞的檢驗，返回的就只有列表余下部分的篩選結(jié)果。
遞歸對開發(fā)者的解放效果或許不像垃圾收集那么顯著，不過它切實地揭示了編程語言的一個重要的發(fā)展方向：通過移交“不確定因素”的控制權(quán)給運行時來消解它們。如果程序員不準(zhǔn)插手列表操作的中間結(jié)果，那么就不會引入那些在交互中產(chǎn)生的錯誤。
尾調(diào)用優(yōu)化
遞歸沒有成為一種平常的操作，其中一個主要原因是棧的增長。遞歸操作一般的實現(xiàn)方式，都是把中間結(jié)果放在棧里，于是沒有為遞歸專門優(yōu)化的語言就會遇到棧溢出的問題。
而像Scala、Clojure這些語言則各自采用了不同的方式來規(guī)避這方面的局限。開發(fā)者也可以使用尾調(diào)用優(yōu)化（tail-call optimization）的寫法來幫助運行時克服棧的增長問題。當(dāng)遞歸調(diào)用是函數(shù)執(zhí)行的最后一個調(diào)用的時候，運行時往往可以在棧里就地更新，而不需要增加新的?？臻g。
很多函數(shù)式語言實現(xiàn)了沒有棧增長的尾遞歸。Erlang用尾遞歸來實現(xiàn)長時間運行的進程，相當(dāng)于運行在應(yīng)用里面的一系列微服務(wù)，它們從別的進程接收消息，并按照消息中的要求來代表別的進程執(zhí)行任務(wù)。這些接收消息并受消息左右的尾遞歸循環(huán)還有調(diào)整微服務(wù)內(nèi)部狀態(tài)的能力，因為對不可變的當(dāng)前狀態(tài)的任何作用結(jié)果，都可以放在表示新狀態(tài)的變量里傳入下一輪遞歸而生效。
遞歸在開發(fā)中用得不多的原因
應(yīng)該部分地歸咎于大多數(shù)命令式語言呆滯的語法配合，讓一件不太容易的事情變得難上加難。函數(shù)式語言的簡潔語法和靈活配合，才使遞歸成為簡單可行的代碼重用選項之一。
