代码之家 › 专栏 › 技术社区 › Sahand

为什么这种方法会导致堆栈溢出错误?

recursion scala

-1

Sahand · 技术社区 · 7 年前

为什么Scala编译器不应用尾部调用优化,除非方法是最终的?

例如:

class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}

结果

错误:无法优化@tailrec注释的方法:它既不是私有的,也不是最终的,因此可以重写

如果应用编译器,到底会出什么问题 TCO 在这种情况下?

0 回复 | 直到 13 年前

Seth Tisue 9 年前

考虑以下与RePL的相互作用。首先,我们用阶乘方法定义一个类:

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

现在,让我们在子类中重写它,使超类的答案加倍:

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

最后一次通话的结果是什么?你可能期望240。但没有:

scala> (new C2).fact(5, 1)
res13: Int = 7680

这是因为当超类的方法进行递归调用时,递归调用通过子类。

如果覆盖的工作方式是240是正确的答案,那么在这里的超类中执行尾部调用优化是安全的。但Scala(或Java)不是这样工作的。

除非方法被标记为最终, 它可能不是在呼唤自己 当它进行递归调用时。

这就是为什么@tailrec不起作用,除非方法是final(或private)。

更新:我建议阅读另外两个答案(约翰和雷克斯的)。

Rex Kerr 15 年前

递归调用可能是子类而不是超类; final 这将防止这种情况发生。但你为什么想要这种行为呢?斐波那契数列没有提供任何线索。但这确实:

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

如果这个漂亮的电话是尾部递归的,我们会打印出来 {Set(0, 1),1} 因为延期不适用。

由于这种递归似乎很有用,并且如果允许对非final方法进行尾部调用,就会被破坏,因此编译器会插入一个真正的调用。

Shawn Mehan 9 年前

允许 foo::fact(n, res) 指出你的日常生活。允许 baz::fact(n, res) 表示其他人凌驾于你的常规之上。

编译器告诉你语义允许 baz::fact() 作为一个包装者也许向上呼叫(?) foo::fact() 如果它想的话。在这种情况下,规则是 foo::事实() ,当它再次出现时,必须激活 事实 而不是 foo::事实() ,而 foo::事实() 尾巴是递归的, 事实 也许不是。此时,不是在尾部递归调用上循环, foo::事实() 必须回到 事实 ,这样它就可以放松自己了。

J D 12 年前

如果编译器在这样的情况下应用TCO,到底会出什么问题?

不会出什么问题的。任何具有适当尾部调用消除的语言(SML、OCaml、F#、Haskell等)都可以做到这一点。Scala不支持的唯一原因是JVM不支持尾部递归,以及Scala通常使用的将尾部位置的自递归调用替换为 goto 在这种情况下不起作用。CLR上的Scala可以像F#一样做到这一点。

Tim 7 年前

对于这个问题,人们普遍接受的答案实际上是误导性的,因为这个问题本身令人困惑。OP没有区分 tailrec 和 TCO 答案并没有解决这个问题。

关键是 对 泰勒克 比要求更严格 总体拥有成本 .

这个 泰勒克 注释要求进行尾部调用 同样的功能 鉴于 总体拥有成本 可用于尾部通话 任何功能 .

编译器可以使用 总体拥有成本 在…上 fact 因为在尾部位置有一个呼叫。具体来说,它可能会扭转局面呼叫到 事实 变成一个跳到 事实 通过适当调整堆栈。这个版本的 事实 与进行调用的函数不同。

因此,公认的答案正确地解释了为什么非终结函数不能 泰勒克 因为不能保证尾部调用是针对同一个函数的,而不是针对该函数的重载版本。但它错误地暗示使用它是不安全的 总体拥有成本 在这种方法上,实际上这是完全安全的,也是一种很好的优化。

[请注意,正如Jon Harrop所解释的,您无法实现 总体拥有成本 在JVM上,但这是编译器的限制,而不是语言的限制,与 泰勒克 ]

作为参考,这里是如何避免问题,而不必制定方法 final :

class C {
  def fact(n: Int): Int = {
    @tailrec
    def loop(n: Int, result: Int): Int =
      if (n == 0) {
        result
      } else {
        loop(n - 1, n * result)
      }

    loop(n, 1)
  }
}

这是因为 loop 是一个具体的函数而不是方法,不能被重写。这个版本还有一个优点,就是消除了虚假信息 result 参数到 事实 .

这是我用于所有递归算法的模式。