Scala似乎需要递归函数的"return"关键字

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

下面是一个代码来检查平衡括号——

使用'return'(工作正常):

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

这是尾递归特有的吗?请帮我理解一下。

正如在一些评论中提到的，您不能只是短路路径并返回没有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)
}

目前实现的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将计算为真或假，但该表达式与代码的其余部分断开连接=>这个函数没有对那个布尔值做任何事情。我们也可以写成val thisAchievesNothing = if (imbalance < 0) then false。我们的thisAchievesNothing将保存一些值，这是有效的语法，但不是很有用。

同样,:

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

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

最后，最后一个if... else if... else也将求值为另一个布尔值，并且由于这个是函数的最后一个表达式，因此只有that和that将是返回值。

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

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

除了公认的答案，还有一些值得考虑的事情:

使用@tailrec，这样你的递归方法得到尾部调用优化的编译器。否则，对于非常大的列表，它可能会产生堆栈溢出。(虽然这里可能不是这种情况，但在实现尾部递归方法时总是考虑使用此注释)。
List是一个单链表，所以它不被索引。在每次递归调用中使用cs(iter)使您的方法在线性时间内获得每个索引的元素。这意味着复杂度是0 (n^2)作为替代方案，要么使用基于索引的chars: Array[Char]，并在0(1)中给出每个元素，要么继续使用列表，但切换到模式匹配。
小问题:if表达式中只有一条语句的多余花括号;parenBalance可以移除，直接调用parenBalanceRecur(char, 0 , 0)作为balance的最后一条语句;parenBalanceRecur使用默认值

我在代码中的建议:

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

相关内容

最新更新

热门标签：