Scala Tutorial - Learn How To Create Tail Recursive Function - scala.util.control.TailCalls._

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 by making use of utilities that Scala provides for tail recursions in the package scala.util.control.TailCalls._

 

As a reminder from the previous tutorial on Tail Recursive Function, 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. Review how to define a tail recursive function

In the previous tutorial on Tail Recursive Function, we showed how to define a tail recursive function named search() which would find a donut item of type String in an Array.

 

Moreover, we used the annotation @annotation.tailrec in order to instruct the compiler to perform any compiler optimisation with regards to stack frame management for this recursive function.


println("\nStep 1: Review 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:

2. Review how to call a tail recursive function

Similarly, let's review how to call the tail recursive function. There is no special syntax for calling the recursive search() function and you simply need to call the function by its name and pass along its parameters.


println("\nStep 2: Review how to call a tail recursive function")
val arrayDonuts: Array[String] = Array("Vanilla Donut", "Strawberry Donut", "Plain Donut", "Glazed Donut")
val found = search("Glazed Donut", arrayDonuts, 0)
println(s"Find Glazed Donut = $found")

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


Step 2: Review how to call a tail recursive function
Find Glazed Donut = Some(true)

 

3. How to define a tail recursive function using scala.util.control.TailCalls._

When it comes to recursion, Scala provides additional utilities in the package scala.util.control.TailCalls._ 

 

Let's go ahead and re-write the recursive search() function from Step 1 by making use of these recursive utilities.


println("\nStep 3: How to define a tail recursive function using scala.util.control.TailCalls._")
def tailSearch(donutName: String, donuts: Array[String], index: Int): TailRec[Option[Boolean]] = {
  if(donuts.length == index) {
    done(None) // NOTE: done is imported from scala.util.control.TailCalls._
  } else if(donuts(index) == donutName) {
    done(Some(true))
  } else {
    val nextIndex = index + 1
    tailcall(tailSearch(donutName, donuts, nextIndex)) // NOTE: tailcall is imported from  scala.util.control.TailCalls._
  }
}

NOTE:

  • We changed the returned type of our function to be TailRec[Option[Boolean]]
  • As a result of using TailRec, we also need to make use of done() in the exit expression if(donuts.length == index) and for the case when we found the donut item else if(donuts(index) == donutName)
  • When recursively calling the function itself, you need to wrap the call to the function inside a tailcall() as follows: tailcall(tailSearch(donutName, donuts, nextIndex))
  • Using the utilities provided by scala.util.control.TailCalls._ is perhaps a bit artificial with regards to our search() function. But, it should help you see how to make use of them.
  • These utilities are the stepping stone to writing Trampoline Recursive Function which we will see in the next tutorial.

4. How to call tail recursive function using scala.util.control.TailCalls._

The syntax to call the recursive function from Step 3 is slightly different as you need to wrap the call inside a tailcall() as shown below:


println("\nStep 4: How to call tail recursive function using scala.util.control.TailCalls._")
val tailFound = tailcall(tailSearch("Glazed Donut", arrayDonuts, 0))
println(s"Find Glazed Donut using TailCall = ${tailFound.result}") // NOTE: our returned value is wrapped so we need to get it by calling result

val tailNotFound = tailcall(tailSearch("Chocolate Donut", arrayDonuts, 0))
println(s"Find Chocolate Donut using TailCall = ${tailNotFound.result}")

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


Step 4: How to call tail recursive function using scala.util.control.TailCalls._
Find Glazed Donut using TailCall = Some(true)
Find Chocolate Donut using TailCall = None

This concludes our tutorial on Learn How To Create Tail Recursive Function - scala.util.control.TailCalls._ 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:

  • Review how to define a tail recursive function
  • Review how to call a tail recursive function
  • How to define a tail recursive function using scala.util.control.TailCalls._
  • How to call tail recursive function using scala.util.control.TailCalls._

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 Trampoline 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