CODEWITHSUNDEEP
scalarecursion
user5505500
user5505500

Reputation:

Understanding the Idea behind Tail Recursion in 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.

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)
}

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

Upvotes: 0

Views: 283

Answers (1)

Jörg W Mittag
Jörg W Mittag

Reputation: 369430

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

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

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.

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.

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()

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

public void foo()
  0: goto 0

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) {}

Gets compiled to:

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)

gets compiled to:

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

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

Upvotes: 3

Related Questions