问scala中的递归非常必要吗？

EN

真正高质量的Scala只需要很少的迭代，只需要稍微多一点的递归。在低级别命令式语言中循环所做的工作通常最好使用高阶组合器，尤其是map和平台图，而且还可以过滤、压缩、折叠、预测、缩减、收集、分区、扫描、groupBy和其他几个方面。迭代最好只在性能关键部分进行，而递归仅在一些高级组合器不太适合(通常不是尾递归，fwiw)的深边情况下进行。在生产系统中编码Scala的三年中，我使用了一次迭代，两次递归，以及大约每天五次映射。

嗯，几个问题合在一起。

递归的必要性

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

一个典型的例子是编写一个函数来返回nth 斐波那契数。下面是一个简单的递归实现：

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

现在，这是低效的(绝对不是尾递归)，但是它的结构与Fibonacci序列的关系是非常明显的。不过，我们可以使其正确地进行尾递归：

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风格for，在这里。

递归解决方案通常比而循环更可取，因为C/C++/风格的循环不返回值，并且需要副作用来实现任何事情(对于C风格的 for 和Java风格的foreach也是如此)。坦率地说，我常常希望Scala从来没有实现过，而(或者把它作为语法糖来实现，比如Scheme的名字叫let)，因为它允许经过传统训练的Java开发人员继续按照他们一贯的方式做事。在有些情况下，有副作用的循环(这就是而给您提供的)是实现某事的更有表现力的方式，但我让相当专注于Java的开发人员不得不达到更难的程度(例如，通过滥用来理解)。

简单地说，传统的，而和的，使笨拙的命令式编码太容易了。如果您不关心这一点，为什么要使用Scala？

堆栈溢出的效率与风险

尾部优化消除了堆叠溢出的风险。将递归解决方案重写为适当的尾递归可能会使它们非常难看(特别是在JVM上运行的任何语言中)。

递归解决方案可能比更命令式解决方案更有效，有时令人吃惊的是。原因之一是它们通常对列表进行操作，其方式只涉及head和tail access。列表上的头和尾操作实际上比对更结构化集合的随机访问操作要快。

动态规划

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

小阴谋家有许多这种迭代式递归编程方法的例子，特别是因为它将早期的解决方案作为子组件重用到以后的、更复杂的解决方案中。我要说，这是动态规划方法的缩影。(这也是有史以来编写得最好的关于软件的教育书籍之一)。我可以推荐它，尤其是因为它同时教你计划。如果你真的不想学习方案(为什么？为什么不呢？)，它已经适应了其他几个语言

如果与匹配

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 (如果是)，请寻找另一种选择。match是一个很好的起点。

我假设，既然您在标题中说的是“递归”，那么在您的问题中也意味着“递归”，而不是“迭代”(不能选择"over /while循环“，因为它们是迭代的:D)。

您可能对阅读有效Scala感兴趣，特别是关于控制结构的部分，该部分主要是回答您的问题。简言之：

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

你的问题的主要问题是它非常广泛。在函数式编程、惯用scala、动态编程等方面，有许多可用的资源，这里没有关于堆栈溢出的答案可以涵盖所有这些主题。这可能是一个好主意，只是在网上漫游一段时间，然后回来提出更具体的问题:)