From Recursion to Tail Recursion in Scala

Tail recursion is a kind of special recursion where the last call in function, calls another function or itself. It is basically a functional form of a loop and is advantageous while the function does not have to wait for the result of inner functions, and does not fill the memory stack. The tail recursion has a fixed stack size and does not lead to a stack overflow. Since most JVM implementations limit the recursion chains to a few thousand frames, deep recursive chains in languages that work on top of the JVM should be implemented tail recursively.

Here is a small example of factorial calculation in recursive and tail recursive implementation.

Recursive call:

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

This implementation reduces the code in following steps:
1 factorial(6)
6 * factorial(5)
6 * (5 * factorial(4))
6 * (5 * (4 * factorial(3)))
6 * (5 * (4 * (3 * factorial(2))))
6 * (5 * (4 * (3 * (2 * factorial(1)))))
6 * (5 * (4 * (3 * (2 * (1 * factorial(0))))))
…
The recursion chaining fills up the stack quickly.

In order to avoid this recursion chain on stack, this tail-implementation can be used:

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

Here’s another example both implementations.

Linear:

def sum2(f: Int => Int)(a: Int, b: Int): Int = {
    if (a>b) 0 else f(a) + sum2(f)(a+1,b)
  }

Tail:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
    def loop(a: Int, acc: Int): Int = {
      if (a>b) acc
      else loop(a+1, f(a)+acc)
    }
    loop(a, 0)
  }           

 
The tail recursion has more lines than linear implementation, but it’s surely more stack efficient.

Cheers!