理解 Scala 尾递归背后的思想 [英] Understanding the Idea behind Tail Recursion in Scala

问题描述

我具有面向对象的背景，主要用 Java 编写应用程序.我最近开始更多地探索 Scala 并且我一直在阅读一些文本.因此，我遇到了一种叫做尾递归的东西.我了解如何编写尾递归方法.

I come from a object oriented background, where I primarily wrote applications in Java. I recently started to explore more on Scala and I have been reading some text. I thus came across something called tail recursion. I understood how to write tail recursive methods.

例如 - 要在 List 中添加元素(当然这可以使用 reduce 方法来完成)但为了便于理解，我写了一个尾递归方法:

For example - To add the elements in a List (Of course this could be done using reduce method) but for the sake of understanding, I wrote a tail recursive method:

@scala.annotation.tailrec
def sum(l: List[Int], acc: Int): Int = l match {
  case Nil => acc
  case x :: xs => sum(xs, acc + x)
}

Scala 运行时如何在内部处理此递归?

How is this recursion handled internally by the Scala run time?

推荐答案

Scala 运行时如何在内部处理此递归?

How is this recursion handled internally by the Scala run time?

不是.它在编译时由编译器处理.

It isn't. It is handled by the compiler at compile time.

尾递归相当于一个 while 循环.因此，尾递归方法可以编译为 while 循环，或者更准确地说，它可以像编译 while 循环一样进行编译.当然，如何准确编译取决于所使用的编译器.

Tail-recursion is equivalent to a while loop. So, a tail-recursive method can be compiled to a while loop, or, more precisely, it can be compiled the same way a while loop is compiled. Of course, how exactly it is compiled depends on the compiler being used.

目前有 Scala 的三种主要实现，它们是 Scala-native(一种以本地机器代码为目标并拥有自己的运行时的编译器)、Scala.js(一种以 ECMAScript 平台为目标的编译器，位于 ECMAScript 运行时之上)，以及 JVM 实现 Scala，它与语言一样令人困惑地也被称为Scala"(面向 JVM 平台并使用 JVM 运行时).曾经有一个 Scala.NET，但不再积极维护.

There are currently three major implementations of Scala, these are Scala-native (a compiler that targets native machine code with its own runtime), Scala.js (a compiler that targets the ECMAScript platform, sitting on top of the ECMAScript runtime), and the JVM implementation Scala which confusingly is also called "Scala" like the language (which targets the JVM platform and uses the JVM runtime). There used to be a Scala.NET, but that is no longer actively maintained.

我将在这个答案中关注 Scala-JVM.

I will focus on Scala-JVM in this answer.

我将使用一个与您略有不同的示例，因为模式匹配的编码实际上相当复杂.让我们从最简单的尾递归函数开始:

I'll use a slightly different example than yours, because the encoding of pattern matching is actually fairly complex. Let's start with the simplest possible tail-recursive function there is:

def foo(): Unit = foo()

这被 Scala-JVM 编译为以下 JVM 字节码:

This gets compiled by Scala-JVM to the following JVM bytecode:

public void foo()
  0: goto 0

还记得我上面说过尾递归等价于循环吗?嗯，JVM 没有循环，它只有 GOTO.这与 while 循环完全相同:

Remember how I said above that tail-recursion is equivalent to looping? Well, the JVM doesn't have loops, it only has GOTO. This is exactly the same as a while loop:

def bar(): Unit = while (true) {}

被编译为:

public void bar()
  0: goto 0

还有一个更有趣的例子:

And for a slightly more interesting example:

def baz(n: Int): Int = if (n <= 0) n else baz(n-1)

被编译为:

public int baz(int);
   0: iload_1
   1: iconst_0
   2: if_icmpgt  9
   5: iload_1
   6: goto      16
   9: iload_1
  10: iconst_1
  11: isub
  12: istore_1
  13: goto       0
  16: ireturn

如你所见，它只是一个 while 循环.

As you can see, it is just a while loop.

这篇关于理解 Scala 尾递归背后的思想的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！