19

阅读专家编写的 Scala 文档可以得到尾递归比 while 循环更好的印象，即使后者更简洁明了。这是一个例子

object Helpers {
    implicit class IntWithTimes(val pip:Int) {
            // Recursive
        def times(f: => Unit):Unit = {
            @tailrec
            def loop(counter:Int):Unit = {
                if (counter >0) { f; loop(counter-1) }
            }
            loop(pip)
        }

            // Explicit loop
        def :@(f: => Unit) = {
            var lc = pip
            while (lc > 0) { f; lc -= 1 }
        }   
    }
}

（需要明确的是，专家根本没有解决循环问题，但在示例中，他们选择以这种方式编写循环，就好像本能一样，这就是我提出的问题：我是否应该发展出类似的本能...... )

while 循环唯一可能更好的方面是迭代变量应该是循环体的局部变量，并且变量的变异应该在一个固定的位置，但 Scala 选择不提供这种语法。

清晰度是主观的，但问题是（尾）递归样式是否提供了改进的性能？

4

3 回答 3

19

我很确定，由于 JVM 的限制，并非每个潜在的尾递归函数都会被 Scala 编译器优化掉，因此对您的性能问题的简短（有时是错误的）答案是否定的。

对您更一般的问题（具有优势）的长答案有点做作。请注意，通过使用while，您实际上是：

  1. 创建一个包含计数器的新变量。
  2. 改变那个变量。

一个接一个的错误和可变性的危险将确保从长远来看，您将引入带有while模式的错误。事实上，您的times功能可以很容易地实现为：

def times(f: => Unit) = (1 to pip) foreach f

这不仅更简单、更小，而且还避免了任何瞬态变量和可变性的创建。事实上，如果您正在调用的函数的类型与结果有关，那么while构造将开始变得更加难以阅读。请尝试使用以下方法实现以下内容whiles：

def replicate(l: List[Int])(times: Int) = l.flatMap(x => List.fill(times)(x))

然后继续定义一个执行相同操作的尾递归函数。

更新：

我听到你说：“嘿！那是作弊！foreach既不是电话while也不是tail-rec电话”。哦真的吗？看看 Scala 对foreachfor的定义Lists：

  def foreach[B](f: A => B) {
    var these = this
    while (!these.isEmpty) {
      f(these.head)
      these = these.tail
    }
  }

如果您想了解有关 Scala 中递归的更多信息，请查看此博客文章。一旦你进入函数式编程，疯狂地阅读 Rúnar 的博客文章。更多信息在这里和这里。

于 2013-09-07T15:31:40.870 回答
6

一般来说，一个直接尾递归函数（即一个总是直接调用自身并且不能被覆盖的函数）总是会被while编译器优化成一个循环。您可以使用@tailrec注释来验证编译器是否能够为特定函数执行此操作。

作为一般规则，任何尾递归函数都可以重写（通常由编译器自动）为while循环，反之亦然。

以（尾）递归风格编写函数的目的不是最大化性能甚至简洁，而是使代码的意图尽可能清晰，同时最大限度地减少引入错误的机会（通过消除可变变量，通常使跟踪函数的“输入”和“输出”变得更加困难）。一个正确编写的递归函数包括对终止条件的一系列检查（使用级联if或else模式匹配）以及在不满足任何终止条件时进行的递归调用（仅当不是尾递归时才复数）。

当有几种不同的可能终止条件时，使用递归的好处最为显着。一系列if条件或模式通常比一个while带有一大堆（可能复杂且相互关联的）布尔表达式的单个条件更容易理解&&，特别是如果返回值需要根据哪个终止条件而有所不同遇见了。

于 2013-09-10T02:19:30.013 回答
4

这些专家是否说性能是原因？我打赌他们的原因更多地与表达性代码和函数式编程有关。你能举出他们论点的例子吗？

递归解决方案比命令式解决方案更有效的一个有趣原因是，它们经常对列表进行操作，并且以仅使用头尾操作的方式进行操作。这些操作实际上比对更复杂集合的随机访问操作更快。

基于 while 的解决方案可能效率较低的另一个原因是，随着问题复杂性的增加，它们会变得非常丑陋……

（我不得不说，在这一点上，你的例子不是一个好例子，因为你的循环都没有做任何有用的事情。你的递归循环特别不典型，因为它什么都不返回，这意味着你错过了关于递归的一个要点函数。功能位。递归函数远不止是重复相同操作n次的另一种方式。）

While 循环不返回值，并且需要副作用来实现任何目标。它是一种控制结构，仅适用于非常简单的任务。这是因为循环的每次迭代都必须检查所有状态以决定下一步。如果有多个潜在的退出路径，loops 布尔表达式也可能变得非常复杂（或者复杂性必须分布在循环中的整个代码中，这可能是丑陋和混淆的）。

递归函数提供了更简洁的实现的可能性。一个好的递归解决方案将一个复杂的问题分解成更简单的部分，然后将每个部分委托给另一个可以处理它的函数 - 诀窍是另一个函数本身（或者可能是一个相互递归的函数，尽管这很少见在 Scala 中 - 与各种 Lisp 方言不同，它很常见 - 因为尾递归支持不佳）。递归调用的函数在其参数中仅接收更简单的数据子集和相关状态；它只返回更简单问题的解决方案。因此，与 while 循环相比，

  • 函数的每次迭代只需要处理问题的一个简单子集
  • 每次迭代只关心它的输入，而不关心整体状态
  • 每个子任务中的成功由处理它的调用的返回值明确定义。
  • 来自不同子任务的状态不会纠缠在一起（因为它隐藏在每个递归函数调用中）。
  • 多个出口点（如果存在）更容易清晰表示。

鉴于这些优点，递归可以更容易地实现有效的解决方案。特别是如果您将可维护性视为长期效率的重要因素。

我要去寻找一些要添加的代码的好例子。同时，在这一点上，我总是推荐The Little Schemer。我会继续解释为什么，但这是两天内该网站上的第二个 Scala 递归问题，所以请查看我之前的答案。

于 2013-09-07T16:28:01.223 回答