progfun1.scala

def pascal1(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal1(c - 1, r - 1) + pascal1(c, r - 1)
}

def pascal2(c: Int, r: Int): Int = {

  @tailrec
  def pascal(n: Int, prev: List[Int]): Int = {
    val row = (0 :: prev).zipAll(prev, 0, 0).map(t => t._1 + t._2)
    if (n == r) row(c)
    else pascal2(n + 1, row)
  }

  if (c <= 0) 1 else pascal2(1, List(1))
}

def pascal3(c: Int, r: Int): Int = {

  def fact(x: Int) = pFact(x, 1)

  def pFact(x: Int, y: Int) = pFact_(x, y, identity)

  @tailrec
  def pFact_(x: Int, y: Int, cnt: Int => Int): Int = {
    if (x <= y) cnt(y)
    else pFact_(x - 1, y, a => cnt(a * x))
  }

  if((c <= 0) || (r <= 0) || (r <= c)) 1
  else pFact(r, c + 1) / fact(r - c)
}

def balance(chars: List[Char]): Boolean = {

  def count(c: Char) = if (c == '(') 1 else if (c == ')') -1 else 0

  @tailrec
  def balance(acc: Int, cs: List[Char]): Boolean = {
    if (acc < 0) false
    else if (cs.isEmpty) acc == 0
    else balance(count(cs.head) + acc, cs.tail)
  }

  balance(0, chars)
}

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

  def count(rest: Int, cs: List[Int]): Int = {
    if (cs.isEmpty || rest < 0) 0
    else if (rest == 0) 1
    else count(rest - cs.head, cs) + count(rest, cs.tail)
  }

  count(money, coins)
}