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.

you've just forgot an else. Every if should have an else... with or without recursion — volia17
– volia17, Commented Jul 5, 2022 at 11:29
You have to make sure that the return value you want is the last value your method produces. Then you don't need (and shouldn't use, for idiomatic Scala code) return. — Jean-Philippe Pellet
– Jean-Philippe Pellet, Commented Jul 5, 2022 at 12:30

Javier Montón · Accepted Answer · 2022-07-05 15:44:00Z

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

Svend · Accepted Answer · 2022-07-05 15:45:41Z

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)

One more thing: watch out for redundant expressions: if (imbalance == 0) then true else false is actually exactly the same expression as imbalance == 0

Alin Gabriel Arhip · Accepted Answer · 2022-07-05 18:18:05Z

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

Collectives™ on Stack Overflow

Scala seems to require 'return' keyword for recursive functions

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related