问尾部递归与头部经典递归

EN

尾部递归==环

您可以使用任何循环并将其表示为尾递归调用。

背景：在纯FP中，一切都必须得到某种价值。scala中的while循环不会产生任何表达式，只会产生副作用(例如更新一些变量)。它只支持来自命令式背景的程序员。Scala鼓励开发人员重新考虑用递归代替while循环，递归总是会产生一些值。

因此，根据Scala：递归是新的迭代。

但是，前面的声明存在一个问题:虽然“常规”递归代码更容易阅读，但它会带来性能损失，并带有溢出堆栈的固有风险。另一方面，tail-recursive代码永远不会导致堆栈溢出(至少在Scala *中是这样)，性能将与循环相同(实际上，我确信Scala将所有尾递归调用转换为普通的旧迭代)。

回到问题上，坚持“常规”递归没有错，除非：

1. 计算大数(堆栈溢出)时使用的算法。
2. 尾部递归带来了显著的性能增益

有两种基本的递归：

1. 头递归
2. 尾递归

在head递归中，函数进行递归调用，然后执行更多的计算，例如使用递归调用的结果。在尾递归函数中，所有的计算都是先进行的，递归调用是最后发生的事情。

这一区别的重要性不会跳出你，但它是极其重要的！想象一个尾部递归函数。它在跑。它完成了所有的计算。作为它的最后一个动作，它准备进行递归调用。在这一点上，堆栈框架的使用是什么？一点也没有。我们不再需要局部变量了，因为我们已经完成了所有的计算。我们不需要知道我们在哪个函数中，因为我们只需要重新输入相同的函数。在尾部递归的情况下，Scala可以消除新堆栈帧的创建，只需重用当前堆栈框架。不管进行多少次递归调用，堆栈都不会变得更深。这就是使尾递归在Scala中特殊的伏都教。

让我们看看这个例子。

 def factorial1(n:Int):Int =
     if (n == 0) 1 else n * factorial1(n -1)


 def factorial2(n:Int):Int = {
      def loop(acc:Int,n:Int):Int =
           if (n == 0) 1 else loop(acc * n,n -1)

     loop(1,n)  
  } 

顺便说一句，有些语言通过将尾递归转换为迭代而不是通过操作堆栈来达到类似的目的。

这不适用于头部递归。你明白为什么吗？想象一个头递归函数。首先它做一些工作，然后进行递归调用，然后做一些更多的工作。当我们进行递归调用时，我们不能仅仅重复使用当前的堆栈框架。在递归调用完成后，我们将需要堆栈帧信息。它有我们的局部变量，包括递归调用返回的结果(如果有的话)。

这里有个问题要问你。示例函数factorial1头递归还是尾递归？那它是干什么用的？(A)检查其参数是否为0。(B)如果是，则返回1，因为0的阶乘为1。(C)如果不是，则返回n乘以递归调用的结果。递归调用是在函数结束之前输入的最后一件事。这是尾部递归，对吗？错误的。进行递归调用，然后n乘以结果，然后返回该乘积。这实际上是头递归(或者中间递归，如果您愿意的话)，因为递归调用不是发生的最后一件事。

欲了解更多信息，请参考链接

在开发软件时，首先要注意的是代码的可读性和可维护性。查看性能特性大多是过早的优化。

在帮助编写高质量的代码时，没有理由不使用递归。

尾递归与普通循环的计数相同。只需看看这个简单的尾递归函数：

def gcd(a: Int, b: Int) = {
  def loop(a: Int, b: Int): Int =
    if (b == 0) a else loop(b, a%b)
  loop(math.abs(a), math.abs(b))
}

它计算两个数的最大公因子。一旦你知道了这个算法，它的工作原理就很清楚了--用while循环来编写它不会让它变得更清楚。相反，您可能会在第一次尝试时引入一个bug，因为您忘记将一个新值存储到一个变量a或b中。

另一方面，可以看到这两种功能：

def goRec(i: Int): Unit = {
  if (i < 5) {
    println(i)
    goRec(i+1)
  }
}

def goLoop(i: Int): Unit = {
  var j = i
  while (j < 5) {
    println(j)
    j += 1
  }
}

哪一个更容易读？它们或多或少是相等的--由于Scalas基于表达式的特性，您获得的用于尾递归函数的所有语法糖都消失了。

对于递归函数，还有另一件事要发挥作用:懒惰的计算。如果您的代码是延迟计算的，它可以是递归的，但不会发生堆栈溢出。请参阅这个简单的函数：

def map(f: Int => Int, xs: Stream[Int]): Stream[Int] = f -> xs match {
  case (_, Stream.Empty) => Stream.Empty
  case (f, x #:: xs)     => f(x) #:: map(f, xs)
}

它会因为大量的投入而崩溃吗？我不这么认为：

scala> map(_+1, Stream.from(0).takeWhile(_<=1000000)).last
res6: Int = 1000001

对Scalas List进行同样的尝试会扼杀您的程序。但是因为Stream很懒，这不是问题。在这种情况下，您也可以编写一个尾递归函数，但一般来说，这并不容易实现。

有许多算法在迭代编写时将不清楚--一个例子是图的深度优先搜索。为了保存需要返回的值，您想自己维护堆栈吗？不，您不会因为它容易出错而且看起来很难看(除了递归的任何定义之外，它还会调用迭代深度优先搜索递归，因为它必须使用堆栈，而“普通”递归也必须使用堆栈--它只是对开发人员隐藏并由编译器维护)。

回到过早优化的问题上，我听到了一个很好的类比:当您有一个无法用Int解决的问题，因为您的数字会变得很大，并且很可能会发生溢出，那么请不要切换到Long，因为这里可能也会出现溢出。

对于递归，这意味着在某些情况下，您可能会炸毁堆栈，但更有可能的情况是，当您切换到仅基于内存的解决方案时，您将得到内存不足的错误。一个更好的建议是找到一种性能不那么差的不同算法。

最后，尝试使用尾递归而不是循环或普通递归，因为它肯定不会杀死堆栈。但是当你能做得更好的时候，就毫不犹豫地把它做得更好。