gal*_*les 11 recursion functional-programming scala
在课程scala教程中,大多数示例都使用自上而下的迭代.部分地,正如我所看到的,迭代用于避免for/while循环.我来自C++,对此感到有些困惑.
迭代选择for/while循环吗？它在生产中是否实用？堆栈溢出的风险是什么？效率怎么样？自下而上动态编程怎么样(特别是当它们不是尾部重复时)？
另外,我应该使用更少的"if"条件,而是使用更多"case"和子类？
Dav*_*ith 20
真正高质量的Scala将使用非常少的迭代并且仅稍微更多的递归.在低级命令式语言中循环操作通常最好使用高阶组合器,尤其是map和flatmap,还有filter,zip,fold,foreach,reduce,collect,partition,scan,groupBy和a好几个人.迭代最好只在性能关键部分进行,而递归仅在高阶组合器不太适合的一些深度边缘情况下完成(通常不是尾递归,fwiw).在生产系统中编写Scala的三年中,我使用迭代一次,递归两次,每天映射大约五次.
its*_*uce 11
嗯,一个问题.
一个经典的例子是编写一个函数来返回第n个 Fibonacci数.这是一个天真的递归实现:
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)(_ + _)
非常简洁,高效,优雅(如果你理解流和懒惰的评价)非常富有表现力.事实上它也是递归的; #::是一个递归函数,但是在懒惰评估的上下文中运行.你当然必须能够递归地想出这种解决方案.
我假设你指的是传统的C风格的,在这里.
递归解决方案通常优于while循环,因为C/C++/Java风格的while循环不返回值并且需要副作用来实现任何内容(对于C-Style for和Java-style foreach也是如此).坦率地说,我常常希望斯卡拉从来没有实现,同时(或已经实施了其作为类似方案的命名让语法糖),因为它允许古典训练的Java开发人员要继续做的事情,他们总是做的方式.在某些情况下,带有副作用的循环,这是,而给你,是一种更有表现力的方式来实现某些东西,但我宁愿Java固定的开发者被迫更难以达到它(例如通过滥用理解).
简单地说,传统的同时,并为化妆笨重势在必行编码太容易了.如果您不关心,为什么使用Scala？
尾部优化消除了堆栈溢出的风险.重写递归解决方案以使其适当地尾递归可能使它们非常难看(特别是在JVM上运行的任何语言中).
递归解决方案可以比更加迫切的解决方案更有效,有时令人惊讶如此.一个原因是他们经常在列表上操作,只涉及头部和尾部访问.列表上的头部和尾部操作实际上比更多结构化集合上的随机访问操作更快.
一个好的递归算法通常会将一个复杂的问题简化为一小组更简单的问题,选择一个来解决并将其余部分委托给另一个函数(通常是对自身的递归调用).现在,对我而言,这听起来非常适合动态编程.当然,如果我正在尝试递归方法解决问题,我通常会从一个天真的解决方案开始,我知道无法解决所有情况,看看它失败的地方,将该模式添加到解决方案并迭代成功.
Little Schemer有许多这种迭代方法用于递归编程的例子,特别是因为它重新使用早期的解决方案作为后续更复杂的子组件.我想说它是动态编程方法的缩影.(它也是有史以来最好的软件教育书籍之一).我可以推荐它,尤其是因为它同时教你Scheme.如果你真的不想学习Scheme(为什么？为什么不呢？),它已经适应了其他一些语言
如果 Scala中的表达式返回值(这非常有用,为什么Scala不需要三元运算符).没有理由避免简单
if (something)
// do something
else
// do something else
表达式.匹配而不是简单if ... else的主要原因是使用case语句的强大功能从复杂对象中提取信息. 这是一个例子.
另一方面,如果......如果......其他如果......其他是一个可怕的模式
无论你在哪里发现你都写了其他的,寻找替代方案. 比赛是一个很好的起点.
我假设，因为您在标题中说了“递归”，所以您在问题中也意指“递归”，而不是“迭代”（不能选择“ over for / while循环”，因为那些是迭代的：D ）。
您可能对阅读Effective Scala感兴趣，特别是有关控制结构的部分，该部分应该可以回答您的问题。简而言之：
递归并不比迭代“好”。对于给定的问题，编写递归算法通常会更容易，然后编写迭代算法（当然，在某些情况下，相反的情况适用）。当“尾部调用优化”可以应用于问题时，编译器实际上将其转换为迭代算法，从而使StackOverflow不可能发生，并且不会影响性能。您也可以在Effective Scala中阅读有关尾部呼叫优化的信息。
您的问题的主要问题是它的范围很广。在函数式编程，惯用的scala，动态编程等方面有许多可用资源，而Stack Overflow上的任何答案都无法涵盖所有这些主题。只是在互连网上漫游一段时间，然后再提出更具体的问题，可能是个好主意:)