Counting change recursive algorithm in Scala

README.md

Scala

Just a few interesting pieces of Scala code

bracketBalance.scala

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

      def loop(chars: List[Char], stack: Int): Boolean = {
        if (chars.isEmpty)  stack == 0 // '(' and ')' should result in 0 if balanced
        else if (chars.head == '(') loop(chars.tail, stack + 1)
        else if (chars.head == ')') loop(chars.tail, stack - 1)
        else loop(chars.tail, stack)

      }

      if (chars.isEmpty) true // if empty, debatable as balanced
      else if (chars.head == chars.last) false // if head and last are equal brackets not balanced
      else loop(chars, 0)

    }

countingChange.scala

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

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

      loop(money, coins)
    }

sumListOfInts.scala

    def sum(xs: List[Int]): Int = {

      def loop(xs: List[Int], prevHead: Int): Int = {

        if (xs.isEmpty) 0
        else if (xs.tail.isEmpty) xs.head+prevHead
        else loop(xs.tail, xs.head+prevHead)

      }

      loop(xs, 0)
  }

balance("())(()") returns true, which is not correct.

Here is my solution:

  def balance(chars: List[Char]): Boolean =
    def _balance(value: List[Char], count: Int): Boolean =
      if count < 0 then false
      else if value.isEmpty then count == 0
      else if value.head == ')' then _balance(value.tail, count - 1)
      else if value.head == '(' then _balance(value.tail, count + 1)
      else _balance(value.tail, count)
    _balance(chars, 0)