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.