两个循环的区别。哪个更有效，为什么？

Question

我碰巧看到 Coursera tutorial Odersky 的 Coursera tutorial。求一个数的阶乘，这是我写的函数。

  def factorial(n: Int): Int = {
    if (n == 0) 1
    else n * factorial(n - 1)
  }

然而当我看到视频时，奥德斯基先生是这样表达的

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

  loop(1, n)
}

他的代码比我的有什么优势？哪个更有效，为什么？

Answer 1

如您所见，这两种解决方案都使用递归。但是第二个示例使用 tail recursion 允许进行一些优化以减少嵌套调用的数量。

More info about tail recursion

Answer 2

两者都是递归，但只有第二个是尾递归，因此是尾的候选者调用优化。如果应用此优化，递归将转换为普通循环（这意味着没有函数调用，因此调用函数的成本被移除）。

在第 1 版中，最后一个运算是乘法，因此编译器无法应用 尾调用优化。

第二个版本使用累加器，所以最后一个操作是递归（递归函数调用）。因此可以应用尾调用优化。

如果添加 @tailrec 注释，编译器将检查 尾调用优化 是否真的应用。

Java 编译器不应用尾调用优化。至于Scala，可以看出"with TCO"和"without TCO"的区别here.

Answer 3

其他人对尾递归的看法是正确的，但我非常喜欢授人以渔。让我们为两个版本计时

object factorial extends App {

  // we need a routine to time
  def time[A](name: String, expr: => A): Unit = {
    val start = System.nanoTime()
    val result = expr
    val time = System.nanoTime() - start

    println(s"$name took $time")
  }

  // non tail recurisve factorial
  def factorial1(n: Int): Int = {
    if (n == 0) 1
    else n * factorial1(n - 1)
  } 

  // tail recurisve factorial
  def factorial2(n : Int): Int = {
    def loop(acc: Int, n: Int): Int = {
      if (n == 0) acc
      else loop(acc * n, n-1)
    }

    loop(1, n)
  }

  //Some driver code
  val n = 200
  time("factorial1", factorial1(n))
  time("factorial2", factorial2(n))

}

在我的盒子上

$ scala factorial
factorial1 took 56000
factorial2 took 20000

（注意，如果我认真地分析这个，我不会运行每个版本一次）

现在让我们看看相关的字节码

$ javap -private -c factorial$.class
Compiled from "factorial.scala"
public final class factorial$ implements scala.App {

但只是相关位。首先，factorial1

public int factorial1(int);
  Code:
     0: iload_1
     1: iconst_0
     2: if_icmpne     9
     5: iconst_1
     6: goto          18
     9: iload_1
    10: aload_0
    11: iload_1
    12: iconst_1
    13: isub
    14: invokevirtual #120                // Method factorial1:(I)I
    17: imul
    18: ireturn

第 14 行递归调用 factorial1

现在factorial2及其内循环方法

public int factorial2(int);
  Code:
     0: aload_0
     1: iconst_1
     2: iload_1
     3: invokespecial #125                // Method loop:(II)I
     6: ireturn

private final int loop(int, int);
  Code:
     0: iload_2
     1: iconst_0
     2: if_icmpne     7
     5: iload_1
     6: ireturn
     7: iload_1
     8: iload_2
     9: imul
    10: iload_2
    11: iconst_1
    12: isub
    13: istore_2
    14: istore_1
    15: goto          0

请注意，内部循环方法 (loop$1) 不会递归调用自身。相反，指令 15 执行 "goto 0" 以直接跳回到内循环的顶部。这就是尾递归的魔力。我们不需要保留一大堆中间结果，我们只需要一点点信息来计算下一件事。

两个循环的区别。哪个更有效，为什么？

Difference in the two loops. Which is more efficient and why?

recursion

scala