Scala Tail Recursion (尾递归)

时间：2022-01-05 16:52:14

Scala对尾递归进行了优化，甚至提供了专门的标注告诉编译器需要进行尾递归优化。不过这种优化仅限于严格的尾递归，间接递归等情况，不会被优化。

尾递归的概念

递归，大家都不陌生，一个函数直接或间接的调用它自己，就是递归了。我们来看一个简单的，计算阶乘的例子。

def factorial(n: Int): Int = {

  if( n <= 1 ) 1

  else n * factorial(n-1)

}

以上factorial方法，在n>1时，需要调用它自身，这是一个典型的递归调用。如果n=5，那么该递归调用的过程大致如下：

factorial(5)

5 * factorial(4)

5 * (4 * factorial(3))

5 * (4 * (3 * factorial(2)))

5 * (4 * (3 * (2 * factorial(1))))

5 * (4 * (3 * (2 * 1)))

120

递归算法，一般来说比较简单，符合人们的思维方式，但是由于需要保持调用堆栈，效率比较低，在调用次数较多时，更经常耗尽内存。 因此，程序员们经常用递归实现最初的版本，然后对它进行优化，改写为循环以提高性能。尾递归于是进入了人们的眼帘。

那么，什么是尾递归？尾递归是指递归调用是函数的最后一个语句，而且其结果被直接返回，这是一类特殊的递归调用。 由于递归结果总是直接返回，尾递归比较方便转换为循环，因此编译器容易对它进行优化。现在很多编译器都对尾递归有优化，程序员们不必再手动将它们改写为循环。

以上阶乘函数不是尾递归，因为递归调用的结果有一次额外的乘法计算，这导致每一次递归调用留在堆栈中的数据都必须保留。我们可以将它修改为尾递归的方式。

def factorialTailrec(n: BigInt, acc: BigInt): BigInt = {

    if(n <= 1) acc

    else factorialTailrec(n-1, acc * n)

}

现在我们再看调用过程，就不一样了,factorialTailrec每一次的结果都是被直接返回的。还是以n=5为例，这次的调用过程如下。

factorialTailrec(5, 1)

factorialTailrec(4, 5)  // 1 * 5 = 5

factorialTailrec(3, 20) // 5 * 4 = 20

factorialTailrec(3, 60) // 20 * 3 = 60

factorialTailrec(2, 120) // 60 * 2 = 120

factorialTailrec(1, 120) // 120 * 1 = 120

120

以上的调用，由于调用结果都是直接返回，所以之前的递归调用留在堆栈中的数据可以丢弃，只需要保留最后一次的数据，这就是尾递归容易优化的原因所在， 而它的秘密武器就是上面的acc，它是一个累加器（accumulator，习惯上翻译为累加器，其实不一定非是“加”，任何形式的积聚都可以），用来积累之前调用的结果，这样之前调用的数据就可以被丢弃了。

出处：http://meetfp.com/zh/blog/tail-recursion

相关文章