Scala Tutorial - Learn How To Create Tail Recursive Function - @annotation.tailrec

By Nadim Bahadoor | Last updated: July 25, 2017 at 13:53 pm

Overview

In this tutorial, we will learn how to create tail recursive function and also make use of the annotation @annotation.tailrec which will instruct the compiler to apply any further optimisation.

 

Tail recursive function will help prevent overflow in your call stack because the evaluation of your looping construct happens at each step.

 

If this does not make any sense at the moment, don't worry we will see an example below.

Steps

1. How to define an Array of type String

Let's start by defining an Array of type String to hold some donut items.


println("Step 1: How to define an Array of type String")
val arrayDonuts: Array[String] = Array("Vanilla Donut", "Strawberry Donut", "Plain Donut", "Glazed Donut")

 

2. How to define a tail recursive function

Next, let's define a tail recursive function named search() which will have the following input parameters:

  • donutName parameter of type String for the donut item to search within the Array
  • donuts parameter of type String Array for the donut items Array
  • index parameter of type Int for the index within the Array on which to run the search
println("\nStep 2: How to define a tail recursive function")
@annotation.tailrec
def search(donutName: String, donuts: Array[String], index: Int): Option[Boolean] = {
  if(donuts.length == index) {
    None
  } else if(donuts(index) == donutName) {
    Some(true)
  } else {
    val nextIndex = index + 1
    search(donutName, donuts, nextIndex)
  }
}

NOTE:

  • The body of the function could have inlined elegantly but we are showing each step verbosely so that it is more clear what the search function is doing.
  • If you have never seen or written a tail recursive function, you can review each step of the function by debugging through. Follow the Debugging Tutorial if you need help with debugging in IntelliJ.
  • The very first expression if(donuts.length == index) is the exit call for the search function because we have looped through all elements within the Array.
  • The second expression else if(donuts(index) == donutName) will exit the search function as we have found the donut item in the Array.
  • In the third expression shown below

val nextIndex = index + 1
search(donutName, donuts, nextIndex)

we increment the current index by 1 and call the search function itself (this is the recursive bit) but for the next item in the Array.

  • The @annotation.tailrec instructs the compiler to add any optimisations with regards to stack frame management as this function is recursive.

3. How to call a tail recursive function

Calling a tail recursive function is not so different than calling any other function. You simply call the function by its name and pass it the corresponding parameters.


println("\nStep 3: How to call a tail recursive function")
val found = search("Glazed Donut", arrayDonuts, 0)
println(s"Find Glazed Donut = $found")

val notFound = search("Chocolate Donut", arrayDonuts, 0)
println(s"Find Chocolate Donut = $notFound")

You should see the following output when you run your Scala application in IntelliJ:


Step 3: How to call a tail recursive function
Find Glazed Donut = Some(true)
Find Chocolate Donut = None

This concludes our tutorial on Learn How To Create Tail Recursive Function - @annotation.tailrec and I hope you've found it useful!

 

Stay in touch via Facebook and Twitter for upcoming tutorials!

 

Don't forget to like and share this page :)

Summary

In this tutorial, we went over the following:

  • How to define an Array of type String
  • How to define a tail recursive function
  • How to call a tail recursive function

Tip

Source Code

The source code is available on the allaboutscala GitHub repository.

 

What's Next

In the next tutorial, I will show you how to create tail recursive function by making use of scala.util.control.TailCalls.

Nadim Bahadoor on FacebookNadim Bahadoor on GithubNadim Bahadoor on LinkedinNadim Bahadoor on Twitter
Nadim Bahadoor
Senior Software Developer | Nephila Capital
Founder of allaboutscala.com. I have over 10 years of experience in building large scale real-time trading systems in the financial industry. Passionate about Distributed Systems, Scala, Big Data and Functional Programming. Stay in touch for upcoming tutorials!
Other allaboutscala.com tutorials you may like:

Share this article on