12

在 coursera scala 教程中，大多数示例都使用自顶向下迭代。部分地，正如我所看到的，迭代用于避免 for/while 循环。我来自 C++，对此感到有些困惑。

是否在 for/while 循环上选择了迭代？在生产中实用吗？stackoverflow的任何风险？效率如何？自下而上的动态编程怎么样（尤其是当它们不是尾部回避时）？

另外，我应该使用更少的“if”条件，而是使用更多的“case”和子类吗？

4

5 回答 5

22

真正高质量的 Scala 将使用非常少的迭代，并且只会使用更多的递归。低级命令式语言中的循环通常最好使用高阶组合器，尤其是 map 和 flatmap，但也可以使用 filter、zip、fold、foreach、reduce、collect、partition、scan、groupBy 和 a好几个人。迭代最好只在性能关键部分进行，递归只在高阶组合器不太适合的一些深度边缘情况下进行（通常不是尾递归，fwiw）。在生产系统中使用 Scala 编码的三年中，我每天使用一次迭代、两次递归和五次映射。

于 2013-09-06T02:28:43.140 回答
12

嗯，几个问题合而为一。

递归的必要性

  1. 递归不是必需的，但它有时可以提供非常优雅的解决方案。
  2. 如果解决方案是尾递归并且编译器支持尾调用优化，那么解决方案甚至可以是高效的。
  3. 正如已经说过的那样，Scala 有许多组合函数，它们可以用来更有表现力和更有效地执行相同的任务。

一个典型的例子是编写一个函数来返回第n 个 斐波那契数。这是一个天真的递归实现：

def fib (n: Long): Long = n match {
  case 0 | 1 => n
  case _ => fib( n - 2) + fib( n - 1 )
}

现在，这是低效的（绝对不是尾递归），但它的结构与斐波那契数列的关系非常明显。不过，我们可以使其正确地尾递归：

def fib (n: Long): Long = {
  def fibloop(current: Long, next: => Long, iteration: Long): Long = {
    if (n == iteration) 
      current
    else
      fibloop(next, current + next, iteration + 1)
  }
  fibloop(0, 1, 0)
}

这本可以写得更简洁，但它是一种有效的递归实现。也就是说，它不如第一个漂亮，而且它的结构与原始问题的关系不太明显。

最后，Luigi Plinge 的基于流的实现从本网站的其他地方被无耻地窃取：

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

非常简洁、高效、优雅并且（如果您了解流和惰性求值）非常富有表现力。事实上，它也是递归的；#::是一个递归函数，但它在惰性求值的上下文中运行。您当然必须能够递归地思考才能提出这种解决方案。

与 For/While 循环相比的迭代

我假设你的意思是传统的 C 风格，这里。

递归解决方案通常比while循环更可取，因为 C/C++/Java 样式的 while 循环不返回值并且需要副作用来实现任何目标（对于 C 样式的 for和 Java 样式的foreach也是如此）。坦率地说，我经常希望 Scala 从未实现while（或将其实现为类似于 Scheme 的命名 let 的语法糖），因为它允许受过经典培训的 Java 开发人员继续按照他们一贯的方式做事。在某些情况下，循环会产生副作用，这就是while给你，是一种更有表现力的方式来实现某事，但我宁愿 Java 固定的开发人员被迫更加努力地实现它（例如，通过滥用for comprehension）。

简单地说，传统的while和for使笨重的命令式编码变得太容易了。如果你不关心这个，你为什么要使用 Scala？

Stackoverflow 的效率和风险

尾部优化消除了 stackoverflow 的风险。将递归解决方案重写为适当的尾递归会使它们变得非常丑陋（尤其是在 JVM 上运行的任何语言中）。

递归解决方案比命令式解决方案更有效，有时令人惊讶。一个原因是它们经常对列表进行操作，其方式仅涉及头部和尾部访问。列表上的头尾操作实际上比结构化集合上的随机访问操作更快。

动态规划

一个好的递归算法通常将一个复杂的问题简化为一小组更简单的问题，选择一个来解决并将其余的委托给另一个函数（通常是对自身的递归调用）。现在，对我来说，这听起来非常适合动态编程。当然，如果我尝试使用递归方法解决问题，我通常会从一个幼稚的解决方案开始，我知道它不能解决所有情况，看看它失败的地方，将该模式添加到解决方案中并迭代成功。

Little Schemer有很多这种递归编程迭代方法的例子，特别是因为它重用了早期的解决方案作为后来更复杂的解决方案的子组件。我会说它是动态编程方法的缩影。（它也是有史以来最好的关于软件的教育书籍之一）。我可以推荐它，尤其是因为它同时教你 Scheme。如果你真的不想学习 Scheme（为什么？你为什么不呢？），它已经适应了其他几种语言

如果与匹配

if表达式，在 Scala 中，返回值（这非常有用，也是 Scala 不需要三元运算符的原因）。没有理由避免简单

if (something)
  // do something
else
  // do something else

表达式。匹配而不是简单的if...else的主要原因是利用 case 语句的强大功能从复杂对象中提取信息。 这是一个例子。

另一方面，if...else if...else if...else是一个糟糕的模式

  1. 没有简单的方法可以查看您是否正确涵盖了所有可能性，即使最后一个else到位。
  2. 如果表达式难以发现，则无意嵌套
  3. 将不相关的条件联系在一起太容易（偶然或通过愚蠢的设计）

无论你在哪里发现你写了else if，寻找一个替代方案。 比赛是一个很好的开始。

于 2013-09-06T13:00:59.707 回答
5

我假设，既然您在标题中说“递归”，那么您在问题中的意思也是“递归”，而不是“迭代”（不能选择“在 for/while 循环中”，因为它们是迭代的：D ）。

您可能有兴趣阅读Effective Scala，尤其是关于控制结构的部分，它应该主要回答您的问题。简而言之：

递归并不比迭代“更好”。通常，为给定问题编写递归算法更容易，然后编写迭代算法（当然也有相反的情况）。当“尾调用优化”可以应用于问题时，编译器实际上将其转换为迭代算法，从而使 StackOverflow 不可能发生，并且不会影响性能。您也可以阅读 Effective Scala 中的尾调用优化。

您的问题的主要问题是它非常广泛。关于函数式编程、惯用 scala、动态编程等有很多可用的资源，而 Stack Overflow 上的任何答案都无法涵盖所有​​这些主题。在互联网上漫游一段时间可能是个好主意，然后带着更具体的问题回来:)

于 2013-09-05T22:27:52.613 回答
2

递归的主要好处之一是它可以让您创建没有变异的解决方案。对于以下示例，您必须计算列表中所有元素的总和。

解决此问题的众多方法之一如下。这个问题的命令式解决方案使用 for 循环，如下所示：

    scala> var total = 0
    scala> for(f <- List(1,2,3)) { total += f }

递归解决方案如下所示：

   def total(xs: List[Int]): Int = xs match {
      case Nil => 0
      case x :: ys => x + total(ys)
}

不同之处在于递归解决方案不使用任何可变临时变量，而是让您将问题分解成更小的部分。因为函数式编程就是编写无副作用的程序，所以总是鼓励使用递归与循环（使用变异变量）。

头递归是一种传统的递归方式，首先执行递归调用，然后从递归函数中获取返回值并计算结果。

通常，当您调用函数时，会将一个条目添加到当前正在运行的线程的调用堆栈中。缺点是调用堆栈有一个定义的大小，所以你可能会得到 StackOverflowError 异常。这就是为什么 Java 更喜欢迭代而不是递归的原因。因为 Scala 运行在 JVM 上，所以 Scala 也存在这个问题。但从 Scala 2.8.1 开始，Scala 通过尾调用优化摆脱了这个限制。你可以在 Scala 中进行尾递归。

回顾递归是函数式编程中避免使用突变的首选方式，其次，Scala 支持尾递归，因此您不会陷入 Java 中的 StackOverFlow 异常。

希望这可以帮助。

于 2013-09-06T01:56:40.913 回答
0

至于堆栈溢出，很多时候你可以通过尾调用消除而侥幸逃脱。

scala 和其他函数范例避免 for/while 循环的原因是它们高度依赖于状态和时间。这使得在正式和精确的庄园中推理复杂的“循环”变得更加困难。

于 2013-09-06T02:05:16.480 回答