迭代 vs 遞迴：用遞迴取代 for 迴圈，看懂 base case 與無狀態
前面幾篇談的都是純函數，上一篇還練習了把不純隔離到程式最外層。這一篇進入函數式工具箱裡的下一個工具：遞迴。
什麼是遞迴函數？
講師說，除了純度之外，函數式程式設計的工具箱裡還需要遞迴（recursion），它是函數式程式設計者最好的朋友。
學員對遞迴函數的回答是「一個會呼叫自己的函數」。講師補充，它是在執行過程中呼叫自己的函數，也可能是間接呼叫自己，例如先呼叫另一個函數，再由那個函數回頭呼叫它。不過在這堂課的函數式世界裡，遞迴函數指的是把自己當作自身計算的一部分的函數。
函數式用遞迴取代迴圈
在命令式程式設計裡，需要重複做某件事時，習慣用 for、while 這類迴圈。函數式程式設計則改用遞迴。
有些純函數式語言甚至根本沒有迴圈。第四篇的純函數裡其實用過迴圈，當時沒問題，因為迴圈被包在具決定性的純函數裡。不過從這一篇開始，為了進入函數式的思維，會盡量避免使用迴圈。
函數式的做法不是在每一輪迴圈裡改變某個變數的值，而是帶著新的值再次遞迴呼叫函數。講師坦言，遞迴是函數式程式設計裡比較燒腦的東西，所以值得花點時間好好想清楚。
迭代：靠會變的狀態重複執行
第二篇把命令式與宣告式擺在對立的兩端，函數式屬於宣告式的一種。命令式的程式是「做這個、做那個、再做另一件事」，它重複執行程式碼的方式是迭代（iteration），也就是某種迴圈：每跑一輪，就改變某個變數的值，例如 for (let a of array) 裡的 a。
這代表迴圈裡有一個值會隨時間改變，第一輪是一個值，第二輪又是另一個值。這種會隨時間改變的值，就是程式的狀態（state），跟第二篇比較物件導向時對狀態的定義一樣。程式裡有會隨時間改變的值時，就是一個**有狀態（stateful）**的程式，那些值在某個特定時間點是什麼，會影響程式的執行。
為什麼函數式要避免狀態
對函數式程式設計者來說，狀態是大忌。值會隨時間改變，就可能無法準確預測函數執行到某個時間點時的狀態，進而帶來意料之外的結果。
講師舉了一個大家可能遇過的情境：以為某個函式庫的方法會回傳某個東西，結果對方改了 API，現在回傳完全不同的東西。一個月前測試全部通過，今天卻失敗了，老闆也很不高興。
狀態會讓人頭痛，所以函數式程式要盡可能做到無狀態（stateless）。這跟第四篇對決定性的要求是同一件事：值會隨時間改變，就沒辦法光看輸入預測輸出。
遞迴：用自我參照取代狀態
不能在 for 迴圈裡改變變數的值，要怎麼重複做某件事？這就是遞迴登場的地方。
遞迴一樣是拿一段計算、用不同的值執行很多次，但不是靠「指派新值給變數」這種有狀態的方式，而是用函數式的方式：
- 迭代：命令式地指示「每跑一輪，就做這個、做那個、再做另一件事」，靠變數的值改變來推進
- 遞迴：函數參照自己，用不同的輸入再執行一次同一段函數程式碼
講師說，這可以看成命令式與函數式的分界，濃縮在「怎麼重複執行程式碼」這個小領域裡。結論是：避免迭代，專注在遞迴。
範例：用迭代寫 sum
先看迭代版本的 sum，它接收一個數字陣列 numbers，回傳所有數字的總和：
js
function sum(numbers) {
let total = 0;
for (i = 0; i < numbers.length; i++) {
total += numbers[i];
}
return total;
}
sum([0, 1, 2, 3, 4]); // 10講師說這是比較老派的 JavaScript 寫法，但能清楚看出 for 迴圈有多麼依賴狀態。sum 先把 total 設成 0，接著進入 for 迴圈。傳統的 for 語法要定義三件事：
- 變數的初始值：
i = 0 - 停止條件：當變數的值，也就是程式的狀態，達到某個條件就停止。這裡是只要
i小於numbers的長度就繼續 - 每一輪的更新：每跑一輪，就用
i++把i加一
迴圈裡針對陣列的每個索引，取出那個位置的數字，再更新 total。
for 迴圈有多命令式
比起較新的 for...of 語法，i++ 更清楚地展現了 for 迴圈「先做這個、再做那個」的命令式本質。我們等於在一步一步告訴 JavaScript：先用 i 等於 0 執行這段程式碼，然後把 i 加一，再檢查條件是否還成立，成立的話就用加一後的值再跑一次。
這些每天都在用的東西裡，其實內建了大量的命令式操作，只是我們可能從來沒想過。就算寫的是 for (let a of array)，底層其實也有一大堆值在命令式地改變。一旦想錯「迴圈跑到這一輪時，各個值應該是什麼」，就很容易在程式碼裡引入意料之外的 bug。
範例：用遞迴寫 sum
再來看遞迴版本的 sum，對外的 API 一樣，接收一個數字陣列 numbers：
js
function sum(numbers) {
if (numbers.length === 1) {
// base case
return numbers[0];
} else {
// recursive case
return numbers[0] + sum(numbers.slice(1));
}
}
sum([0, 1, 2, 3, 4]); // 10函數一開始先做判斷，決定要走哪一個分支。講師說，除非想讓電腦當掉，不然每個遞迴函數都需要兩樣東西：
- 遞迴情況（recursive case）：函數呼叫自己的情況。如果沒有這種情況，它就不叫遞迴函數了
- 基本情況（base case）：不遞迴的情況，這點特別重要，千萬不能忘記
沒有 base case 會怎樣
如果只有遞迴情況，函數就會不停地遞迴、遞迴、再遞迴下去。學員有人說「會掉進《全面啟動》的虛空裡」，也有人答出正解：stack overflow。
在 Firefox 的實作裡，這個錯誤訊息甚至直接寫著「too much recursion」，講師笑說這等於在罵「壞壞的函數式程式設計者」。所以才需要 base case。用《全面啟動》來比喻，base case 就像夢中夢中夢的最底層，也就是那顆陀螺。
sum 的兩個情況
在 sum 裡，base case 是陣列只剩一個數字的時候。如果給一個只有一個數字的陣列，要求算出總和，答案就是陣列裡那唯一的值，不需要再呼叫 sum。
其他比較長的陣列都會落入遞迴情況：
- 用
numbers[0]取出第一個元素 - 用
numbers.slice(1)取得剩下的元素，對這個比較小的陣列再次呼叫sum - 陣列一次比一次短，直到只剩一個數字，進入 base case
到了 base case 之後，就從遞迴呼叫一層一層跳出來：把回傳的結果加上前一層取出的數字，再跳出一層、再加上前一個數字，直到得出最後的總和。
整個過程沒有改變任何變數的值。每一層呼叫拿到的都是一個新的、更短的陣列，靠的是不同的輸入，而不是會隨時間改變的狀態。
遞迴需要練習
講師說，如果本來就習慣寫遞迴函數，那很好，接下來會覺得很輕鬆。如果不習慣，開始思考怎麼把平常用命令式迭代做的事，改成用函數式遞迴實作時，腦袋可能會有點痛。這也是接下來要一起練習的原因。
複習
遞迴函數必備的兩個組成是什麼？
遞迴函數需要遞迴情況（函數呼叫自己的情況）與基本情況（base case，不遞迴的情況，用來停止遞迴、避免 stack overflow）。
在函數式程式設計中，遞迴和迭代有什麼不同？
遞迴是用不同的輸入呼叫函數本身來多次執行計算，過程中不改變狀態；迭代則是在迴圈裡改變變數的值。
為什麼函數式程式設計者偏好遞迴而不是迴圈？
遞迴能在不改變變數值的情況下多次執行計算，避免有狀態的寫法，而有狀態的寫法可能讓程式的行為難以預測。
如果遞迴函數只有遞迴情況、沒有 base case，會發生什麼事？
函數會無止盡地呼叫自己，最後導致 stack overflow 錯誤。
在遞迴版本的 sum 裡，陣列的總和是怎麼算出來的？
取出第一個元素，對剩下比較小的陣列遞迴呼叫函數，再在遞迴呼叫一層層返回時，把每個元素加上去。
遞迴函數缺少 base case 可能造成什麼問題？
函數會造成 stack overflow。
函數式程式設計者認為程式裡的狀態有什麼問題？
狀態會讓程式的執行變得難以預測。
用遞迴加總陣列時，函數通常怎麼拆解問題？
取出第一個元素，再遞迴處理剩下的陣列。
什麼是遞迴函數？
把自己當作自身計算一部分、會呼叫自己的函數。
小測驗
遞迴函數必備的兩個組成是什麼？
遞迴情況（函數呼叫自己）與 base case（停止遞迴的非遞迴情況）在函數式程式設計中，遞迴和迭代有什麼不同？
遞迴用不同的輸入呼叫自己來重複計算、不改變狀態；迭代則在迴圈裡改變變數的值為什麼函數式程式設計者偏好遞迴而不是迴圈？
遞迴能避免有狀態的寫法，而狀態會讓程式行為難以預測如果遞迴函數只有遞迴情況、沒有 base case，會發生什麼事？
函數會無止盡地呼叫自己，造成 stack overflow在遞迴版本的 sum 裡，陣列的總和是怎麼算出來的？
取出第一個元素，對剩下的陣列遞迴呼叫，在遞迴返回時把元素加總 遞迴函數缺少 base case 可能造成什麼問題？
函數會造成 stack overflow函數式程式設計者認為程式裡的狀態有什麼問題？
狀態會讓程式的執行變得難以預測用遞迴加總陣列時，函數通常怎麼拆解問題？
取出第一個元素，再遞迴處理剩下的陣列什麼是遞迴函數？
把自己當作自身計算一部分、會呼叫自己的函數此文章是 FrontendMasters 上的 Functional JavaScript First Steps, v2 課程筆記
