尾递归（或尾递归？）是一种特定类型的递归。特别是，如果对自身的调用作为函数的最后一个动作发生，则称递归函数使用尾递归。

为了更好地理解，假设我们要编写一个递归函数def sum(n: Int): Long，如果我们传递参数n = 5，那么结果是以下总和：5 + 4 + 3 + 2 + 1 = 15。

让我们比较两种不同的方法来实现这个算法，第一种使用常规递归函数，第二种使用尾递归。

1.正常递归函数

def sum(n: Int): Long =
    if (n <= 0)
        0
    else
        n + sum(n - 1)

在这种情况下，函数不使用尾递归，因为虽然递归调用sum(n - 1)出现在函数的末尾，但它实际上并不是最后一个动作。实际上，要完成该语句，您必须先执行，sum(n - 1)然后需要将结果添加到的附加步骤n。

2. 带尾递归的递归函数

def sum(n: Int, total: Long = 0): Long =
    if (n <= 0)
        total
    else
        sum(n - 1, total + n)

虽然这个函数产生与前一个函数相同的结果，但这个函数可以说是使用尾递归，因为递归sum(n - 1, total + n)调用是函数的最后一个动作。

递归函数是否使用“尾递归”有什么关系？

当递归函数多次调用自身时，调用会累积在调用堆栈上，这本身效率不高，因为它会消耗内存。但更糟糕的是，如果在这个堆栈上积累了太多的调用，它最终会溢出调用堆栈并抛出异常java.lang.StackOverflowError。

如果我们执行具有非常高值的正常递归函数，我们可以观察到这一点：n

println(sum(1000000))

正常递归函数演示

结果：

java.lang.StackOverflowError
  at Rextester$.sum(source.scala:12)
  at Rextester$.sum(source.scala:12)
  at Rextester$.sum(source.scala:12)
  ...

对于像 Scala 这样提倡使用递归函数的函数式语言来说，这种低效率是一个严重的问题。

但是，当 Scala 检测到递归函数使用尾递归时，编译器能够自动对代码执行优化，有效地完全删除递归并用一个简单的循环替换它。这种优化通常称为尾调用优化。

暂时使用 Java 语法，就好像编译器将带有尾递归的递归函数转换为以下没有递归的代码（或多或少）：

long sum(int n) {
    long total = 0;
    while(true) {
        if (n <= 0) {
            return total;
        } else {
            total += n;
            n -= 1;
        }
    }
}

由于这种自动转换，无论分配给 的值如何，内存使用量都保持不变，并且完全避免n了调用堆栈溢出 ( ) 的风险：StackOverflowError

println(sum(1000000))

带有尾递归的递归函数演示

结果：

500000500000

结论

由于 Scala 对带有尾递归的递归函数进行了自动优化，因此值得尝试在可能的情况下调整递归函数的算法以使用尾递归。特别是，如果函数进行多次递归调用，这样做很重要，以避免消耗过多的内存，甚至溢出调用堆栈。

请注意，包括 Java 在内的许多其他编程语言不包括这种自动优化。但是由于 Scala 是一种促进递归函数的自由使用的函数式语言，因此编译器包含这种优化以尽量减少其对性能和内存的影响是有意义的。

此外，即使我们使用不包含这种自动优化的另一种编程语言，也最好了解尾递归是什么。因为有时需要手动优化递归函数以纠正内存问题或调用堆栈溢出。在这些情况下，关键是找到一种方法来重新设计函数的逻辑以使用尾递归。如果这可以实现，那么手动将逻辑转换为使用循环而不是递归是微不足道的。

编辑——使用@tailrec注解确保使用“尾递归”

Scala 允许您使用@tailrec( scala.annotation.tailrec) 注释来注释递归函数。通过添加此注释，编译器验证递归函数确实使用尾递归，如果不是，则给您一个错误。这是确认函数将受益于自动优化并且我们在函数设计中没有犯错误的好方法。

要了解它是如何工作的，让我们再次使用上面的 2 个递归函数，并为它们添加注释。首先，正常的递归函数：

@tailrec def sum(n: Int): Long =
    if (n <= 0)
        0
    else
        n + sum(n - 1)

带有注释的普通递归函数的演示@tailrec

结果：

Error(s), warning(s):
source_file.scala:13: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
            n + sum(n - 1)
              ^
one error found

如我们所见，编译器警告我们该函数不使用尾递归。

但是，如果我们现在将注释应用于使用尾递归的递归函数：

@tailrec def sum(n: Int, total: Long = 0): Long =
    if (n <= 0)
        total
    else
        sum(n - 1, total + n)

带有注释的尾递归的递归函数演示@tailrec

结果：

500000500000

在这种情况下，编译器没有返回错误，确认该函数确实使用了尾递归，并且它将受益于编译器的自动优化。

@sstan 已经很好地回答了它，所以我不会深入研究尾端递归优化是什么。只需评论它既不比您所谓的normal recursion好也不差。它在某些情况下有其优势，但编译器最好选择实现递归的最佳方式。

调用函数会创建一个新的环境来执行函数的代码。这种环境被称为闭包（closure），在任何函数式语言中都是必不可少的。从面向对象编程的角度来看，您还可以将闭包视为函数的实例，而将函数视为类。

每次调用函数时，都会创建一个闭包，该闭包将保持活动状态，直到函数退出。多亏了这个闭包，函数可以调用其他函数，并通过将被调用函数替换为返回值（这被称为“引用透明度”）来继续执行它。同样，由于闭包保持其执行状态，因此可以拦截我们调用的函数中产生的错误，从而尝试纠正它们。

对于调用自身的函数（也称为“递归调用”），每次调用都会创建与前一次几乎相同的闭包。如果我们确定这个调用在调用队列的末尾，或者什么相同，如果我们可以将调用堆栈替换为返回值而不需要做更多的操作，那么就可以使用单个关闭函数的所有调用。通过这种方式，我们将不必生成所有闭包来节省资源，尽管作为交换，我们将失去捕获错误的可能性和具有“惰性评估”的优势。

“懒评价”这件事值得一提。如果仅计算获得结果所必需的值，则称评估是惰性的。函数式编程的特点之一就是能够尽可能地将计算推迟到操作序列的末尾，从而丢弃不会影响最终结果的操作。

编译器的当前状态（在函数式编程中）已经允许我们推断哪些操作是不需要执行的，或者哪些优化可以改进执行（tailrec opt、内联调用等）。一般来说，编译器会在我们可以提供的帮助下创建最佳版本。

例如，我们可以给出斐波那契函数的以下定义：

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

这个定义不会是tailrec。我们可以创建一个版本：

@tailrec 
def fib(n: Int, v: BigInt=0, acc: BigInt=1): BigInt =
  if (n == 0)
    acc
  else
    fib(n-1, acc, acc+v)

这个tailrec版本不会有内存问题，并且可能会比以前的版本快得多。仍然不是最好的版本。为了给出想法，您可以保存中间结果，这样您就不必总是计算它们，代价是花费更多的内存（也称为“记忆化”）。

但是让我们看看另一个懒惰的版本：

val fib: Stream[BigInt] =
  BigInt(1) #:: BigInt(1) #:: (fib zip fib.tail) map {case (a,b) => a+b}

我们是fib根据自身来定义的，它给出了一个无限的序列。使用Streams的特点是它的扩展是在我们发现新元素时进行的（惰性求值），并在计算元素时存储它们。这是一种计算斐波那契数列的简单方法，并且比之前的tailrec版本更有效。

我希望我已经为你澄清了一些事情。