Scala – Tail Recursion

  • date 27th April, 2021 |
  • by Prwatech |
  • 0 Comments

Tail Recursion in Scala

 

The tail recursive function are effective than non tail recursive functions since tail-recursion can be enhanced by compiler. A recursive function is supposed to be tail recursive if the recursive call is the last thing done by the function. There is no reason to keep record of the past state.  

tail recursion function uses a package import scala.annotation.tailrec  in the program.

technique used in functional programming languages like Scala to optimize recursive functions by eliminating unnecessary stack frames. In Scala, a function is tail-recursive if the recursive call is the last operation performed in the function body. This allows the Scala compiler to optimize the function into an iterative loop, avoiding stack overflow errors that can occur with traditional recursion.

Scala provides the @tailrec annotation, which instructs the compiler to check if the function is tail-recursive. If the function meets the criteria for tail recursion, the compiler transforms it into a loop using an iterative process, rather than pushing new stack frames onto the call stack.

Tail recursion is particularly useful for writing clean and efficient recursive algorithms in Scala, such as factorial calculations, list processing, and tree traversal. By leveraging tail recursion, developers can write recursive functions that are both elegant and performant, taking advantage of Scala’s functional programming features while avoiding the limitations of traditional recursive approaches. Understanding and utilizing tail recursion is essential for writing idiomatic and efficient Scala code.

use case 1:

// Scala program of GCD using recursion
import scala.annotation.tailrec
object prwatech {
// Function defined
def GCD(x: Int, y: Int): Int =
{
// tail recursion function defined
@tailrec def gcd(a:Int, b:Int): Int=
{
if (b == 0) a
else gcd(b, a % b)
}
gcd(y, x)
}
// Main method 
def main(args:Array[String]) 
{ 
    println(GCD(5, 10)) 
}   
}

output:

5

use case 2:

// Scala program of factorial with tail recursion
import scala.annotation.tailrec
object eduprwa {
// Function defined
def factorial(n: Int): Int =
{
// Using tail recursion
@tailrec def factorialAcc(acc: Int, n: Int): Int =
{
if (n <= 1)
acc
else
factorialAcc(n * acc, n - 1)
}
factorialAcc(1, n)
}
// Main method 
def main(args:Array[String]) 
{ 
    println(factorial(6)) 
} 
}

output:

720

use case 3:

// Scala program of factorial with tail recursion
import scala.annotation.tailrec
object eduprwa {
// Function defined
def factorial(n: Double): Double =
{
// Using tail recursion
@tailrec def factorialAcc(acc: Double, n: Double): Double =
{
if (n <= 1)
acc
else
factorialAcc(n * acc, n - 2)
}
factorialAcc(1, n)
}
// Main method 
def main(args:Array[String]) 
{ 
    println(factorial(5.4)) 
} 
}

output

25.70400000000001

0
0

Quick Support

image image