Home »
Scala language
Tail Recursion in Scala
Tail recursion in Scala is a recursive method that was created to make the Classic recursion more efficient. In this tutorial on tail recursion in Scala, we will learn about tail recursion in depth along with examples.
Submitted by Shivang Yadav, on September 04, 2019
Scala Tail recursion
A special type of recursion which does the recursive call as the last thing in the execution of the code. This tail recursion allows the compiler to optimize the program.
Let's dig deep into what tail recursion is?
The tail recursion is a recursion that initiates from last. It is better than the normal (non-tail) recursion as the compiler is able to optimize it, i.e. take less time and memory while executing the recursion.
A tail-recursive function takes only single space in the stack as compared to the memory required by normal recursion that takes one stack space for each recursion.
Syntax:
To call a tail-recursive method, use the following import statement,
import scala.annotation.tailrec
Syntax to define a tail recursive function,
@tailrec def function_name (parameter list) : return_type = {
//code to be executed
}
This syntax is used to define a tail-recursive function but for using it you need to import it from a package. And the code will call the function in the last segment of the function.
Example:
import scala.annotation.tailrec
object Factorial
{
def fact(n: Int): Int =
{
@tailrec def calFact(acc: Int, n: Int): Int =
{
if (n <= 1)
acc
else
calFact(n * acc, n - 1)
}
calFact(1, n)
}
def main(args:Array[String])
{
println("The factorial of 8 is " + fact(8))
}
}
Output
The factorial of 8 is 40320
Explanation:
This program is used to calculate the factorial of a given number, (8 in this case). In the main section, we will call a method fact() which has a tail-recursive function calFact which does the work of calculating value.