原始的問題
話說我在 Coursera 上修了一門 Functional Programming Principles in Scala 的課，第三週的作業 TweetSet 有一項是要利用一個每次都會回傳最大值的函式，來實作出一個建立遞增的 List 的遞迴函式。
因為常常在 Scala 裡面利用遞迴的方式建立列表，所以我很自然的就寫出了像下面這樣的程式碼：
var mySet = Set(3, 4, 1, 6, 5)
def buildingList(resetSet: Set[Int]): List[Int] = {
def building(resetSet: Set[Int], accumulator: List[Int]): List[Int] = {
if (resetSet.isEmpty) {
accumulator
} else {
var max = resetSet.max
building(resetSet - max, max :: accumulator)
}
}
building(resetSet, Nil)
}
assert(buildingList(mySet) == List(6, 5, 4, 3, 1)) // Ooops!
當然，這樣程式碼做的不是我們想要的東西，由於我們使用的是 prepend（作業裡唯一提供給我們加入新元素到 List 的方法），所以建出來的 List 的順序會和 input 的順序相反。
轉換過後的問題
雖然現在看起來我的腦袋大概生鏽了，不過一開始我真的搞了很久還是不知道怎麼樣讓建出來的 List 和 input 的順序相同。
不過後來我突然發現，這個問題其實和下面的問題一模一樣，如果可以解下面的問題（根本就是每次程設課程教的第一個遞迴函式啊……orz），那麼就可以建立一個和 input 順序一樣的 List 了。
定義一個如下的遞迴函式（不使用 inner function / helper function 或 accumulator），回傳值是 n 的階乘：
def factorial(n: Int): Int = { .... }也就是說當呼叫 factorial(6) 的時候，應該要回傳 6 * 5 * 4 * 3 * 2 * 1，其中值得注意的是 2 * 1 應該是第一個被實際運算並簡化成整數的運算式。
這個程式碼的模式在最一開始的幾個課程影片中就有，如果可以理解這個範例的話，就會發現其實兩個是一模一樣的問題，只要進行以下的代換就好了：
- 在 factorial(n: Int): Int 會變成 buildingList(n: Set[Int]): List[Int]
- factorial 的中止條件是 n == 1，但 buildingList 的中止條件是 n 是空集合
然後我們只要再問自己下面的問題：
- 在 factorial 中遇到中止條件 (n == 1) 的時候我們返回的是 1，但在 buildingList 中遇到了空集盒的時候，要返回什麼？
- 在 factorial 中我們使用 * 這個運算子來連接所有的整數值，在 buildingList 中我們要用什麼來連接所有的整數值。
礙於課程的 honor code，我不能直接貼完整的程式碼，但這樣的提示應該非常夠解決這個問題了。事實上，當我發現這是和遞迴寫階乘同樣的問題的時候，我覺得自己真是蠢斃了。
回響