Home » Scala

Tail Recursion in Scala

By IncludeHelp Last updated : October 10, 2024

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 of Tail recursion

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]): Unit = {
    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.