Scala seems to require 'return' keyword for recursive functions

Question

I'm new to Scala and know that the 'return' keyword is redundant. However, when writing a recursive function, the control doesn't return from a call stack when the desired condition is met if the 'return' keyword is missing.

Below is a code to check for balanced parentheses -

Using 'return' (works fine):

  def balance(chars: List[Char]): Boolean = {
    def parenBalance(char : List[Char])  :Boolean = {
      parenBalanceRecur(char, 0 , 0)
    }

    def parenBalanceRecur(charSequence: List[Char], itr : Int, imbalance : Int) : Boolean = {
      if (imbalance < 0) then return false
      if (itr == charSequence.length ) {
        if (imbalance == 0) then return true else return false
      }

      if (charSequence(itr) == '(')  {
        parenBalanceRecur(charSequence, (itr + 1), (imbalance + 1))
      }
      else if (charSequence(itr) == ')') {
        parenBalanceRecur(charSequence, itr + 1, imbalance -1)
      }
      else {
        parenBalanceRecur (charSequence, itr +1, imbalance)
      }
    }
    parenBalance(chars)
  }

Without return (Successfully computes #1, but doesn't return, fails at #2 with IndexOutOfBoundsException):

  def balance(chars: List[Char]): Boolean = {
    def parenBalance(char : List[Char])  :Boolean = {
      parenBalanceRecur(char, 0 , 0)
    }

    def parenBalanceRecur(charSequence: List[Char], itr : Int, imbalance : Int) : Boolean = {
      if (imbalance < 0) then  false
      if (itr == charSequence.length ) {
        if (imbalance == 0) then true else false // #1
      }

      if (charSequence(itr) == '(')  {  // # 2
        parenBalanceRecur(charSequence, (itr + 1), (imbalance + 1))
      }
      else if (charSequence(itr) == ')') {
        parenBalanceRecur(charSequence, itr + 1, imbalance -1)
      }
      else {
        parenBalanceRecur (charSequence, itr +1, imbalance)
      }
    }
    parenBalance(chars)
  }

Is this specific to tail recursion? Please help me understand this.

Answer 1

Besides the accepted answer, some things worth considering:

• use @tailrec, so your recursive method gets tail-call optimized by the compiler. Otherwise it can produce stack overflow for very large lists. (Although this might not be the case here, always consider using this annotation when implementing tail-recursive methods).
• List in Scala is a singly-linked list, so it's not indexed. Using cs(iter) on each recursive call makes your method get the element in linear time for every index. That means you'll get O(n^2) complexity. As an alternative, either use chars: Array[Char] which is indexed-based and gives you each element in O(1) or continue using list but switch to pattern match instead.
• minor things: redundant curly braces from if expressions with only a single statement inside; parenBalance can be removed and call directly parenBalanceRecur(char, 0 , 0) as the last statement in balance; use default values for parenBalanceRecur.

My suggestions in code:

  def isBalanced(chars: List[Char]): Boolean = {
    @tailrec
    def balance(cs: List[Char], imbalances: Int = 0): Boolean =
      if (imbalances < 0) false
      else cs match {
          case Nil => imbalances == 0
          case x :: xs =>
            if (x == '(') balance(xs, imbalances + 1)
            else if (x == ')') balance(xs, imbalances - 1)
            else balance(xs, imbalances)
        }

    balance(chars)
  }

  println(isBalanced("()".toList))          // true  
  println(isBalanced("()(())".toList))      // true
  println(isBalanced(")(".toList))          // false
  println(isBalanced("(()))".toList))       // false
  println(isBalanced("((((()))))".toList))  // true

Answer 2

As currently implemented, parenBalanceRecur() has 3 top-level if expressions, they each evaluate to a boolean value, but the rule in scala is that only the last expression of the function is the return value of the function => the first two are simply ignored.

=> in your second implementation:

def parenBalanceRecur(charSequence: List[Char], itr : Int, imbalance : Int) : Boolean = {
      if (imbalance < 0) then  false
      if (itr == charSequence.length ) {
        if (imbalance == 0) then true else false // #1
      }

      if (charSequence(itr) == '(')  {  // # 2
        parenBalanceRecur(charSequence, (itr + 1), (imbalance + 1))
      }
      else if (charSequence(itr) == ')') {
        parenBalanceRecur(charSequence, itr + 1, imbalance -1)
      }
      else {
        parenBalanceRecur (charSequence, itr +1, imbalance)
      }
    }
    parenBalance(chars)
  }

The first expression if (imbalance < 0) then false will evaluate to either true or false, but this expression is disconnected from the rest of the code => the function is not doing anything with that boolean. We could as well write val thisAchievesNothing = if (imbalance < 0) then false. Our thisAchievesNothing will hold some value, which is valid syntax, but is not very useful.

Likewise, this:

if (itr == charSequence.length ) {
        if (imbalance == 0) then true else false // #1
      }

will evaluate to another boolean that is equally ignored.

Finally, the last if... else if... else will also evaluate to yet another boolean, and since this one is the last expression of the function, that and that only will be the returned value.

Try to re-writing parenBalanceRecur as one single if.. else if... else if ... expression instead of 3, and then the behavior will be the same as the implementation that uses return.

(we tend to avoid return since it's a statement that does something, whereas the habit is to write functions/expression that are some value)

Answer 3

As mentioned in some comments, you can not just short circuit the path and return a value without the return keyword. return is not needed only at the last value of the method. In any case, usually, it's a good practice to avoid short circuits with multiple returns in a method. In your example, adding two else you can construct the path down to the last value of each possible output without using the return keyword:

def balance(chars: List[Char]): Boolean = {
  def parenBalance(char : List[Char])  :Boolean = {
    parenBalanceRecur(char, 0 , 0)
  }

  @tailrec
  def parenBalanceRecur(charSequence: List[Char], itr : Int, imbalance : Int) : Boolean = {
    if (imbalance < 0) then false
    else if (itr == charSequence.length ) {
      if (imbalance == 0) then true else false // #1
    }

    else if (charSequence(itr) == '(')  {  // # 2
      parenBalanceRecur(charSequence, (itr + 1), (imbalance + 1))
    }
    else if (charSequence(itr) == ')') {
      parenBalanceRecur(charSequence, itr + 1, imbalance -1)
    }
    else {
      parenBalanceRecur (charSequence, itr +1, imbalance)
    }
  }
  parenBalance(chars)
}