Scala : implement recfun

1 files changed, 20 insertions, 3 deletions

diff --git a/Scala/recfun/src/main/scala/recfun/Main.scala b/Scala/recfun/src/main/scala/recfun/Main.scala
index 277aa1a..b8ac271 100644
--- a/Scala/recfun/src/main/scala/recfun/Main.scala
+++ b/Scala/recfun/src/main/scala/recfun/Main.scala
@@ -14,15 +14,32 @@ object Main {
   /**
    * Exercise 1
    */
-  def pascal(c: Int, r: Int): Int = ???
+  def pascal(c: Int, r: Int): Int =
+    if (c == 0 || c == r) 1 else pascal(c-1, r-1) + pascal(c, r-1)
 
   /**
    * Exercise 2
    */
-  def balance(chars: List[Char]): Boolean = ???
+  def balance(chars: List[Char]): Boolean = {
+    def balanceR(chars: List[Char], depth: Int): Boolean =
+      if (chars.isEmpty) depth == 0
+      else if (chars.head == '(') balanceR(chars.tail, depth + 1)
+      else if (chars.head == ')') {
+        if (depth == 0) false
+        else balanceR(chars.tail, depth - 1)
+      }
+      else balanceR(chars.tail, depth)
+    balanceR(chars, 0)
+  }
 
   /**
    * Exercise 3
    */
-  def countChange(money: Int, coins: List[Int]): Int = ???
+  def countChange(money: Int, coins: List[Int]): Int = {
+    if (money == 0) 1                                   // successful recursion
+    else if (money < 0) 0                               // too far
+    else if (coins.isEmpty) 0                           // no more coins
+    // use this coin (one more time) or not anymore
+    else countChange(money - coins.head, coins) + countChange(money, coins.tail)
+  }
 }