# From Recursion to Tail Recursion in Scala

#scala #recursion #optimization

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!