title: How to balance parenthesis recursively
body: <p>I'm working on some code to balance parenthesis, <a href="https://stackoverflow.com/questions/2711032/basic-recursion-check-balanced-parenthesis">this question</a> proved most useful for the algorithm.</p>
  
  <p>I implemented it in my first language (PHP) but I'm learning Scala and trying to convert the code.</p>
  
  <p>Here is my PHP code:</p>
  
  <pre><code>function balanced($string) {
    return isBalanced($string, "");
  }
  
  function isBalanced($chars, $stack) {
    if (!strlen($chars))
      return empty($stack);
  
    switch ($chars[0]) {
      case '(':
        // prepend stack with '(', move to next character
        return isBalanced(substr($chars, 1), $chars[0] . $stack);
      case ')':
        // if '(' seen previously, shift stack, move to next character
        return !empty($stack) &amp;&amp; isBalanced(substr($chars, 1), substr($stack, 1));
      default:
        // do nothing to stack, move to next character
        return isBalanced(substr($chars, 1), $stack);
    }
  } 
  </code></pre>
  
  <p>I've test this, it works. However, when I convert it to Scala, it fails on balanced strings.</p>
  
  <p>My Scala code:</p>
  
  <pre><code>object Main {
    def balance(chars: List[Char]): Boolean = {
      def balanced(chars: List[Char], stack: String): Boolean = {
        if (chars.isEmpty)
          stack.isEmpty
        else if (chars.head == ')')
          balanced(chars.tail, chars.head + stack)
        else if (chars.head == '(')
          !stack.isEmpty &amp;&amp; balanced(chars.tail, stack.tail)
        else
          balanced(chars.tail, stack)
      }
  
      balanced(chars, "")
    }
  }
  </code></pre>
  
  <p>I appreciate this isn't the best Scala code but I'm just starting out. Some tests:</p>
  
  <pre><code>balance("(if (0) false (x))".toList) - fails
  balance("profit and loss (P&amp;L).\n(cashflow)".toList) - fails
  balance(":)".toList) - passes
  balance(")(()".toList) - passes
  </code></pre>
  
  <p>The PHP equivalent passes all these tests. What have I done wrong in my Scala implementation?</p>