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!

### Like this:

Like Loading...

## Published by dzhamzic

bits & notes
View all posts by dzhamzic