Google News
logo
Scala - Interview Questions
What is Recursion tail in Scala?
In Scala, tail recursion is a technique used to optimize recursive functions. It allows recursive functions to be implemented in a way that avoids stack overflow errors and provides efficient execution.

A recursive function is said to be tail-recursive when the recursive call is the last operation performed in the function, without any further computation. In other words, the recursive call is in the "tail position" of the function. This enables the Scala compiler to optimize the recursive function by converting it into an iterative loop, eliminating the need for additional stack frames.

To make a recursive function tail-recursive, the Scala programming language provides an annotation called `@tailrec`. When applied to a recursive function, the `@tailrec` annotation helps ensure that the function is tail-recursive and triggers a compilation error if the function cannot be optimized.

Here's an example to illustrate the concept of tail recursion in Scala:
import scala.annotation.tailrec

def factorial(n: Int): Int = {
  @tailrec
  def factorialHelper(n: Int, acc: Int): Int = {
    if (n <= 1)
      acc
    else
      factorialHelper(n - 1, acc * n)
  }

  factorialHelper(n, 1)
}

val result = factorial(5)
println(result) // Output: 120​
In this example, the `factorial` function calculates the factorial of a given number `n`. The `factorialHelper` function is defined inside the `factorial` function and marked with the `@tailrec` annotation.

The `factorialHelper` function takes two parameters: `n` for the current number and `acc` for the accumulated result. It uses a recursive approach to calculate the factorial by multiplying the current number with the accumulated result.

Since the recursive call `factorialHelper(n - 1, acc * n)` is the last operation performed in the function, it is tail-recursive. The `@tailrec` annotation ensures that the function is optimized for tail recursion by the compiler.

By using tail recursion, the factorial function can calculate the factorial of large numbers without causing a stack overflow error, as the recursive calls are optimized into a loop-like structure, utilizing constant stack space.

It's important to note that the `@tailrec` annotation only guarantees the tail-recursive optimization if the function meets the required criteria. If the function doesn't fulfill the tail recursion conditions (such as having additional computations after the recursive call), the annotation will result in a compilation error.
Advertisement