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)
  }

Could someone explain to me the intuition behind countChange function? I don't understand it!

@dksifoua :
"Could someone explain to me the intuition behind countChange function? I don't understand it!"

Exercise 3: Counting Change
Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.

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)