15

听 Scala 课程和解释我经常听到：“但在实际代码中，我们使用的不是递归，而是尾递归”。

这是否意味着在我的真实代码中我不应该使用递归，但尾递归非常类似于循环并且不需要史诗般的短语“为了理解递归，你首先需要了解递归”。

实际上，考虑到您的堆栈……您更有可能使用类似循环的尾递归。

我错了吗？这种“经典”递归是否仅适用于教育目的，让您的大脑回到大学时代？

或者，尽管如此，我们可以在某个地方使用它......递归调用的深度小于 X（其中 X 是您的堆栈溢出限制）。或者我们可以从经典递归开始编码，然后，害怕有一天你的堆栈被炸毁，应用几个重构来使它像尾巴一样，以便在重构领域更强大？

问题：您将使用/在您的真实代码中使用“经典头”递归的一些真实样本，可能尚未重构为尾一，也许？

只是为了好玩，找到了关于该主题的漂亮图片

4

4 回答 4

8

尾递归 == 循环

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

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

所以根据 Scala：递归是新的迭代。

但是，前面的语句存在一个问题：虽然“常规”递归代码更易于阅读，但它会带来性能损失，并且存在溢出堆栈的固有风险。另一方面，尾递归代码永远不会导致堆栈溢出（至少在 Scala* 中），并且性能将与循环相同（事实上，我确信 Scala 会将所有尾递归调用转换为普通的旧迭代）。

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

  1. 您在计算大数时使用的算法（堆栈溢出）
  2. 尾递归带来了显着的性能提升
于 2013-11-10T05:21:54.650 回答
2

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

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

尾递归与正常循环的计算相同。看看这个简单的尾递归函数：

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循环编写它不会让它更清楚。相反，您可能会在第一次尝试时引入错误，因为您忘记将新值存储到变量之一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因为这里很可能也会溢出。

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

作为结论，尝试更喜欢尾递归而不是循环或正常递归，因为它肯定不会杀死你的堆栈。但是，当您可以做得更好时，请不要犹豫，做得更好。

于 2013-11-10T12:02:17.743 回答
2

递归有两种基本类型：

  1. 头递归
  2. 尾递归

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

这种区别的重要性并不会突然出现在您身上，但它非常重要！想象一个尾递归函数。它运行。它完成了所有的计算。作为它的最后一个动作，它已准备好进行递归调用。在这一点上，堆栈帧的用途是什么？一个都没有。我们不再需要我们的局部变量，因为我们已经完成了所有的计算。我们不需要知道我们在哪个函数中，因为我们只是要重新输入相同的函数。 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 乘以结果，并返回此乘积。这实际上是头递归（或中间递归，如果您愿意），因为递归调用并不是最后发生的事情。

有关更多信息，请参阅链接

于 2016-07-24T18:18:25.960 回答
1

如果您不处理线性序列，那么尝试编写一个尾递归函数来遍历整个集合是非常困难的。在这种情况下，为了可读性/可维护性，您通常只使用普通递归。

一个常见的例子是二叉树数据结构的遍历。对于每个节点，您可能需要在左右子节点上重复。如果您要尝试以递归方式编写这样的函数，首先访问左侧节点，然后访问右侧，您需要维护某种辅助数据结构来跟踪需要访问的所有剩余右侧节点。但是，您可以仅使用堆栈来实现相同的目标，并且它会更具可读性。

这方面的一个例子是iteratorScala 的RedBlack树中的方法：

def iterator: Iterator[(A, B)] =
  left.iterator ++ Iterator.single(Pair(key, value)) ++ right.iterator
于 2013-11-10T22:48:18.940 回答