Functions are an integral part of modern programming languages. In OOP they are called methods; in a functional world their name is functions, as you may guess. I’ve already published multiple articles about Scala functions. In this post, I want to speak exactly about recursive functions.

Let’s start with the definition. A recursive function is a function which calls itself. That’s why it’s important to have some condition for stopping. Of course, that is if you don’t want to create an infinite loop.

Recursion could be applied to many common problems, which you are used to solving with the help of regular `loops` for and `while`. For example, how to calculate the sum of numbers between two numbers? We create an array of all elements and then iterate through it, adding all elements.

``````def standardSum(a: Int, b: Int): Int = {
if (a > b) 0
else {
var result = 0
for (number <- a to b)
result += number
result
}
}

//55
standardSum(0, 10)``````

The same result can be achieved with help of recursive function:

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

//55
recursiveSum(0, 10)``````

As you see we return expression `a + recursiveSum(a+1, b)` until all elements would be added.

The second approach is more concise, but it has a point of risk – java.lang.StackOverflowError. Since recursion is interpreted by the JVM as a regular Java method invocation, it implies usage of one additional frame in the stack per a recursive call. So if the number of recursive calls exceeds the limit of the stack, the StackOverflow error occur.

Tail Recursion

If you want to be sure that a recursive function would not cause the `StackOverflowError`, you need to transform it in a tail recursion. What is a tail recursion? Tail recursion is a function where the last action is the invocation of a recursive function. Sounds tricky. Let’s consider an example:

``````def sum(a: Int, b: Int): Int = {

@tailrec
def tailRecursionSum(a: Int, b: Int, result: Int): Int = {
if (a > b)
result
else
recursiveSum(a+1, b, result + a)
}

recursiveSum(a, b, 0)
}

//55
sum(0, 10)``````

In the code above we declared a function inside of another function. The annotation `@tailrec` indicates that the function is a tail recursion. It’s not mandatory, but it validates that the function is developed as a tail recursion.

Thank to Scala tail recursion optimization, we don’t fear the exception `StackOverflowError`, because on the JVM level this code interprets as a regular loop.

So a tail recursion in Scala is more efficient than a regular recursion. In order to confirm this, I’d like to demonstrate a function which calculates a greatest common divisor. Of course I’ll use a tail recursion:

``````@tailrec
def gcd(a: Int, b: Int): Int = {
if (b == 0) a
else gcd(b, a % b)
}

//9
gcd(18, 27)``````

Try to illustrate each step of the execution for yourself in order to understand how it works. 