Scala 筆記5 - tail recursion & counting change problem

Tail Recursion

這篇文章把tail calls 和 tail recursion講得很清楚：
http://www.ruanyifeng.com/blog/2015/04/tail-call.html

tail recursion的好處就是可以讓stack frame消耗數目維持跟iteration loop一樣。

雖然Scala 會對tail recursion做optimization，但是tail recursion不一定是最好的coding style，因為除非像是計算factorial那樣會累積非常多stack frames (deep recursion chain)，造成可能的stack overflow， 否則基本上還是要以程式碼的簡潔和效率為主，通常不用寫成tail recursion。

一個非tail recursion的factorial function如下：

def factorial(x:Int): Int = {

  if (x == 0)
    1
  else    x*factorial(x-1)
}

如果改寫成tail recursion版本，我們會需要一個accumulator來達成。

def facTail(x:Int): Int = {

  def loop(x:Int, acc:Int): Int = {
    if (x == 0)
      acc
    else      loop(x-1, acc*x)

  }

  loop(x, 1)

}

Counting Change Problem

有各種幣值的零錢一袋，幣值coins以List[Int]表示，請問任意金額n，有幾種這些幣值的組合方式？此function的signature如下：



def countChange(money: Int, coins: List[Int]): Int




老實說，這個問題我寫過兩次，一次就是之前上的Coursera Scala課程，另一次是自修SCIP 使用Scheme的時候，結果我現在還是無法想出解題邏輯，慚愧殘念。



SCIP原文的解題邏輯如下：



"To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin.  But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind. 



所以要從coins中組合出n的方法數等於下兩者的和

(1) 使用了幣值x的方法數

(2) 沒使用幣值x的方法數



如果寫成集合來看：

(1) = | { {x,... }, {x,...}, ...} |

(2) = |total set| - (1)



由於(1)的set是可以組合出n的所有組合，如果把每個組合中的x拿掉一個，並不會改變這個set的數目，而這個新的set其實就是組合出(n-x)的所有組合！不了解這個關鍵就無法寫出recurrence。



因為這個recurrence在(1)的時候就會把n減少，如果n在某個回合變成零，代表達成一次幣值組合，這就是我們的base case。完整implementation如下：





def countChange(money: Int, coins: List[Int]): Int = {

  if (coins.isEmpty || money < 0)
    return 0
  if (money == 0)
    return 1
  countChange(money - coins.head, coins) + countChange(money, coins.tail)
}