Scala似乎需要递归函数的“返回”关键字。

Question

我是Scala的新手，我知道“返回”关键字是多余的。但是，在编写递归函数时，如果“返回”关键字丢失，则当满足所需条件时，控件不会从调用堆栈返回。

下面是一个代码，以检查是否有平衡括号-

使用“返回”(工作正常)：

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

如果没有返回(成功计算#1，但不返回，则在#2处使用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)
  }

这是针对尾递归的吗？请帮我理解一下。

Answer 1

正如目前实现的那样，parenBalanceRecur()有3个顶级if表达式，每个表达式都计算为一个布尔值，但是scala中的规则是，函数的最后一个表达式是函数=>的返回值--前两个表达式被忽略。

第二个实现中的=>：

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

第一个表达式if (imbalance < 0) then false将计算为true或false，但该表达式与代码=>的其余部分断开连接--函数没有使用该布尔值执行任何操作。我们也可以写val thisAchievesNothing = if (imbalance < 0) then false。我们的thisAchievesNothing将保存一些值，这是有效的语法，但不是很有用。

同样，这也是：

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

将计算为另一个同样被忽略的布尔值。

最后，最后一个if... else if... else也将计算为另一个布尔值，因为这个布尔值是函数的最后一个表达式，所以它只会是返回的值。

尝试将parenBalanceRecur重写为一个单一的if.. else if... else if ...表达式，而不是3，然后行为将与使用return的实现相同。

(我们倾向于避免使用return，因为它是一种做某事的语句，而习惯是编写一些有价值的函数/表达式)

Answer 2

正如在一些注释中提到的，您不能只在没有return关键字的情况下短路路径并返回一个值。仅在方法的最后一个值时才需要return。在任何情况下，通常，这是一个很好的做法，以避免短路的多重回报在一个方法。在您的示例中，添加两个else，您可以构造到每个可能输出的最后一个值的路径，而无需使用return关键字：

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

Answer 3

除了公认的答案外，还有一些值得考虑的问题：

• 使用@
• ，因此您的递归方法将得到编译器优化的尾调用。否则，它可能会对非常大的列表产生堆栈溢出。(虽然这里可能不是这样的，但是在Scala中实现尾递归methods).
• List是一个单链接列表时，请始终考虑使用这个注释，因此它没有被索引。对每个递归调用使用cs(iter)使您的方法能够在线性时间内获得每个索引的元素。这意味着你会得到O(n^2)的复杂性。作为另一种选择，要么使用基于索引并为O(1)中的每个元素提供的chars: Array[Char]，要么继续使用list，但转而切换到模式匹配。
• 的次要内容:从if表达式中删除只包含一个语句的冗余大括号；可以删除parenBalance并直接调用parenBalanceRecur(char, 0 , 0)作为balance中的最后一条语句；为balance使用默认值。

我在代码中的建议：

  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