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:

• Feel free to review the previous tutorial on Tail Recursive Function for additional details on the recursive search() function above.

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