GNU 是 GNU is not UNIX! 的縮寫。
--- 維基百科

天氣放晴了，但風吹在身上卻開始有些涼意了。

一邊說著差不多該是離開前往下一個城市的時候，小動物又一直碎唸著天氣冷了想吃有熱湯又有肉的東西再走。真是麻煩的傢伙。

我一直很好奇招牌上說的那個祖傳的湯是怎麼一回事，小動物說。

在我們知道了函式是一種可以呼叫的東西。而且函式可以被指派給變數，可以當做其它函式呼叫時的參數，也可以回傳函式之後，我們還要理解函式的一個特性：遞迴。

遞迴

遞迴基本上就是在函式的定義裡，有呼叫自己的動作。例如這樣的函式：

// JavaScript 語法
function dontRunIt(x) {
  let y = x + 1
  return dontRunIt(y) //這裡呼叫了自己！
}

dontRunIt(1)

是可以定義並執行，但是(概念上)永遠都不會結束的。因為每一步那個 x 會被加上 1，接著當成下一步的 x 來呼叫。如果真的執行下去，運氣好的會把魔法記憶暫存區的空間擠爆然後整個停止，運氣不好的話嘛…

我們來看能正常運作的遞迴吧。

重要的，是什麼時候停下來

我們試著用遞迴的方式，把一個陣列加總吧。

// JavaScript 語法
function sum(source) {
  if (source.length === 0) {
    return 0
  } else {
    let [head, ...tail] = source
    return head + sum(tail)
  }
}

sum([1, 2, 3]) //=> 6

第一次遇到遞迴，我們一步步拆開來看：

1. 定義完函式後，有人呼叫了 sum，並把 [1, 2, 3] 當參數傳進函式。
2. 進入函式後，source 會被替換成 [1, 2, 3]。
3. 因為 source 不是空的，所以長度會大於 0，跳過第 3 行進入 else 區塊。
4. source 被拆成 head 是 1, tail 是 [2, 3]
5. 留著 1 + 的部份，用 tail，也就是 [2, 3] 當做參數，呼叫下一輪的 sum。
6. 一樣不是空陣列，進入 else, 切成 head 是 2，tail 是 [3]。
7. 留著 2 + 的部分，下一輪呼叫 sum 的參數是 tail，[3]。
8. 一樣不是空陣列，進入 else, 切成 head 是 3，tail 是 []。
9. 留著 3 + 的部分，下一輪呼叫 sum 的參數是 tail，[]。
10. source 終於是空陣列了，回傳 0
11. 我們拿到了 (1 + (2 + (3 + (0)))，可以加總了，拿到結果： 6

尾遞迴

雖然這樣可以運作，但是重新看一下上面的步驟，我們有好幾步的敘述是「留著 x+，接著用 y 當參數進行下一輪的呼叫」。而這個「留著」的行為，事實會在魔法運作的暫存空間裡記著一筆記錄。這次的輸入只有三個，影響不大，但一般來說當術式運作時，若遞迴超過二、三十層，那麼法術的反應速度會明顯的變慢。

想解決這個問題，我們要用到一個技巧，叫做尾遞迴 (tail recursive)。訣竅是每一次遞迴中，回傳的那行，只能是一個可以直接回傳的值，或是單純的函式呼叫。像是這樣：

// JavaScript 語法
function tailRecursiveSum(source, accu) {
  if(source.length === 0) {
    return accu;
  } else {
    let [head, ...tail] = source
    return tailRecursiveSum(tail, accu + head)
  }
}

tailRecursiveSum([1, 2, 3], 0) //=> 6

我們把函式改成接受兩個參數，而其中一個是用來累加的值，接下來每一圈只要做到這兩件事，最後一步就會是個單純的函式呼叫：

1. 取出一個元素，讓下一步要處理的資料變短一個 (也就是 tail)。
2. 把取出的元素跟累加器相加。

而這麼一來魔法運作時不需要多記錄什麼等一下要回來處理的東西，而是在每一步都把函式呼叫代換成新的參數，在最後一步直接回傳結果。

當我們在尾遞迴加總的範例裡，看到了 source 跟 accu。而每一步的計算就是把 accu 跟拿到的元素相加。那麼，我們是不是可以把這個相加的計算也抽出來，讓其它人可以任意的替換成他們想要的計算方式，相乘也好相減也好。那麼大家只要傳入 source 、累加器、以及每一步的累加方式，就自動進行尾遞迴了？

把計算也抽象化

應該可以猜到了吧？這個把計算部份抽象做出來的自動遞迴用法術，就是… reduce。那麼，你想要自己試試看嗎？

// JavaScript 語法
function myReduce(source, accu, f) {
  // ?
}

myReduce([1, 2, 3], 0, (accu, x) => accu + x) //=> 應該要拿到 6

(防雷分隔線)

(防雷分隔線)

(防雷分隔線)

(防雷分隔線)

讓我看看你寫的…喔喔喔雖然花了一段時間，但是很棒啊！嗯？想看我寫的？

// JavaScript 語法
function myReduce(source, accu, f) {
  if (source.length === 0) {
    return accu //當 source 為空時表示已經折完了，回傳累加器(最終結果)
  } else {
    //否則先把 source 切成頭跟尾巴, 倒數第二步時，尾巴會是空串列
    let [head, ...tail] = source;
    return myReduce(tail, f(accu, head), f); //遞迴
    //三個參數分別是 (尾巴, 呼叫 f 產生這一步的累加, f 本身要繼續傳下去)
  }
}

myReduce([1, 2, 3, 4, 5], 1, (accu, i) => accu * i) //=> 120

於是我們現在知道只要某個國家的函式能夠遞迴，我們就可以像組合積木一樣，先組出 reduce，再組出 map 及 filter… 一路下去將各種好用的高階函式逐個組裝出來了。

至此，我們已經知道很多有趣的概念了，但是函數式程式設計的核心想法，並非僅是只靠用函式的方式來操作而己。雖然表面上看起來很像是如此，但是就像上次說的，觀點不同，就會得出不同的理解與做法。而更深入的部份，只待在這個莊園裡是很難體會的。

而等你理解了其它的概念之後，回來這個莊園或是其它國家，就能夠不眩目於表面的操作或特定的字詞，而是用更深一層的角度來思考跟解決事情。

所以，想跟我一起往下走，繼續這趟旅程嗎？

於是我們跟學院的人們道別，離開莊園，啟程前往神領 Haskell。

在走了好長一段路後，喧嘩聲遠去而回頭已看不見來時的圍牆。忽然有一條刺眼的弧線，從很遠很遠的地方拋射過來，在前方的荒涼草原上，舖開一整片光的平面。

而當光漸漸柔和下來，就看見在那暖亮的表面，鋼筋與磚塊及各式各樣的建材自平面向上自行組合堆疊並不斷拔高，在短時間內，一幢幢的高樓重覆著建立崩壞建立的過程向上伸展，而整座架構於光流上的城市就在我們眼前逐漸但確實的成形…

我轉頭看小動物，它的表情看起來蠻複雜的。似乎有點開心，但又帶著一絲猶豫。

沒想到這會在這種時候跑到這邊來。

「那個，究竟是什麼？」

Elixir 之城，分散的不沉堡壘。

[to be continue]