Scala 递归思考(上)

Scala 递归

参考资料
1. https://codeday.me/bug/20171011/84027.html
2. http://blog.csdn.net/jasonding1354/article/details/50525735
3. 《快学 Scala》
4. 《深入理解 Scala》
5. 《图解算法》
6. https://twitter.github.io/scala_school/zh_cn/collections.html#fold

1 递归与函数式编程

在函数式编程中，递归是随处可见的，递归比在命令式编程中更为重要。递归是表达函数的最常用方式，但是也有两个缺点：

• 反复调用函数带来的开销
• 栈溢出的风险

栈在这里是一个重要的编程概念，要理解递归，必须理解什么是栈。计算机内部使用被称为调用栈的栈。使用栈虽然很方便，但是也要付出代价，存储详尽信息可能要占用大量的内存，每个函数调用都占用一定内存的话，如果栈很高，意味着计算机存储了大量函数调用的信息，一般情况下，会有两种选择：

• 转成循环
• 使用尾递归

嵌套方法是指一个很长的方法里还有其他「辅助」方法，阶乘是比较常见的需要辅助方法的情况。

import scala.annotation.tailrec
def factorial(i: Int): Long = {
    @tailrec
    def fact(i: Int, accumulator: Int): Long = {
        if (i <= 1) accumulator
        else fact(i - 1, i * accumulator)
    }
    fact(i, 1)
}
factorial: (i: Int)Long 
(0 to 5) foreach(i => println(factorial(i)))

尾递归表示调用递归函数是该函数中最后一个表达式，该表达式的返回值就是所调用的递归函数的返回值。尾递归非常重要，因为这是把函数优化为循环的最重要的一种递归。循环可以消除潜在栈溢出的风险，同时也因为消除了函数调用开销而提升效率。原生的 JVM 还不支持尾递归优化，但 scalac 可以支持。

Scala 编译器对尾递归做了有限的优化。为了排除在生产环境中出现栈空间的崩溃，可以加一个 tailrec 关键词，编译器会告诉你代码是否正确地实现了尾递归的。如果 fact 不是尾递归，编译器就会抛出错误。

2 递归和尾递归

递归函数的核心是设计好递归表达式，并且确定算法的边界条件。要写出尾部递归并不容易，函数设计需要下苦心。

// 阶乘递归
def factorial(n: BigInt): BigInt = {
  if (n <= 1) 1 else n * factorial(n - 1)
}
// 阶乘尾递归
import scala.annotation.tailrec
def factorialTailRecursive(n: BigInt): BigInt = {
  @tailrec
  def _loop(acc: BigInt, n: BigInt): BigInt =
    if (n <= 1) acc else _loop(acc * n, n - 1)
  _loop(1, n)
}
// 菲波那切数列递归
def fibonacci(n: Int): Int =
  if (n <= 2) 1 else fibonacci(n - 1) + fibonacci(n - 2)
// 菲波那切数列尾递归
def fibonacciTailRecursive(n: Int): Int = {
  @tailrec
  def _loop(n: Int, acc1: Int, acc2: Int): Int =
    if (n <= 2) acc2 else _loop(n - 1, acc2, acc1 + acc2)
  _loop(n, 1, 1)
}
// 求列表长度尾递归
def lengthTailRecursive[A](ls: List[A]): Int = {
  @tailrec
  def lengthR(result: Int, curList: List[A]): Int = curList match {
    case Nil => result
    case _ :: tail => lengthR(result + 1, tail)
  }
  lengthR(0, ls)
}

3 Scala 中使用到的尾递归

在较旧的版本的 Scala 集合中有几个方法操作集合，foldLeft 和 reduceLeft 有一个比 foldRight 和 reduceRight 重大的优势，它们是尾递归的，可以在 Scala 的尾递归优化中获益。还记得尾递归必须是一次队规中最后一个运行的操作吗？
在 Scala 2.12.2 中，这个性能优势被取消了，因为都是用到了尾递归。（未考证，待查）

@tailrec
private def foldl[B](start: Int, end: Int, z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)
@tailrec
private def foldr[B](start: Int, end: Int, z: B, op: (A, B) => B): B =
if (start == end) z
else foldr(start, end - 1, op(this(end - 1), z), op)
override /*TraversableLike*/
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, length, z, op)
override /*IterableLike*/
def foldRight[B](z: B)(op: (A, B) => B): B =
foldr(0, length, z, op)
override /*TraversableLike*/
def reduceLeft[B >: A](op: (B, A) => B): B =
if (length > 0) foldl(1, length, this(0), op) else super.reduceLeft(op)
override /*IterableLike*/
def reduceRight[B >: A](op: (A, B) => B): B =
if (length > 0) foldr(0, length - 1, this(length - 1), op) else super.reduceRight(op)