Scala - Tail Recursion

Quiz

This chapter takes you through the concept of tail recursion in Scala programming. Tail recursion optimizes recursive functions where you do not need more stack frames to execute the program. So, you can write efficient recursive functions.

Tail Recursion

Tail recursion is a technique where the recursive call is the last operation in the function. The compiler in Scala can optimize tail-recursive functions to avoid stack overflow errors. So it is as efficient as iterative solutions in Scala.

The recursive call is the final action in the function. So, the Scala compiler can optimize this last recursion. You can reuse the current stack frame for each recursive call.

Syntax

The syntax of tail-recursive function in Scala is -

@scala.annotation.tailrec
def functionName(params: Type): ReturnType = {
   // base case
   if (condition) baseResult
      // recursive case
   else functionName(newParams)
}

Example of Tail Recursion

The following example shows defining and using a tail-recursive function in Scala programming -

object Demo {
   @scala.annotation.tailrec
   def factorial(n: Int, acc: Int = 1): Int = {
      if (n <= 1) acc
         else factorial(n - 1, n * acc)
   }

   def main(args: Array[String]): Unit = {
      println(factorial(5)) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

In the example, the factorial method is tail-recursive. The recursive call to factorial is the last operation. The Scala compiler can optimize this recursion.

Advantages of Tail Recursion

Tail recursion is more efficient than normal recursion. Tail-recursion has several advantages and disadvantages. The disadvantage is that if the iterative version of the same program is more efficient, then tail-recursion does not make sense. Because the iterative program does not need any additional stack, but its tail recursive program will always need a stack to store the function calls.

So, its tail recursive program takes up more memory. Therefore, the Scala compiler can convert a tail recursive program into its equivalent iterative program for efficiency purposes.

The advantage of a tail-recursive program is that it can avoid stack overflow. It is easy to convert a tail-recursive program into its equivalent iterative program. Tail recursion may be suitable for processing large data sets.

Example of Non-Tail Recursion

The Tower of Hanoi is a classic example of a problem that uses non-tail recursion. The recursive call is not the last operation. So it is non-tail-recursive.

Syntax

The syntax of non-tail-recursive function in Scala is -

def functionName(params: Type): ReturnType = {
   // base case
   if (condition) baseResult
   // recursive case
   else {
      // some operations
      functionName(newParams)
     // more operations
   }
}

Example

object Demo {
   def towerOfHanoi(n: Int, from: String, to: String, aux: String): Unit = {
      if (n == 1) {
         println(s"Move disk 1 from $from to $to")
      } else {
         towerOfHanoi(n - 1, from, aux, to)
         println(s"Move disk $n from $from to $to")
         towerOfHanoi(n - 1, aux, to, from)
      }
   }

   def main(args: Array[String]): Unit = {
      towerOfHanoi(3, "A", "C", "B")  
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

In the example, the towerOfHanoi function is non-tail-recursive. It has more non-recursion action after recursion.

Tail Recursion with Multiple Parameters

You can have multiple parameters in tail-recursive functions. So you can pass more state information through the recursive calls.

Syntax

The syntax of tail-recursive function with multiple parameters is -

@scala.annotation.tailrec
def functionName(param1: Type1, param2: Type2, ...): ReturnType = {
   // base case
   if (condition) baseResult
   // recursive case
   else functionName(newParam1, newParam2, ...)
}

Example

Consider the example of tail recursion with multiple parameters in Scala programming -

object Demo {
   @scala.annotation.tailrec
   def gcd(a: Int, b: Int): Int = {
      if (b == 0) a
         else gcd(b, a % b)
   }

   def main(args: Array[String]): Unit = {
      println(gcd(54, 24))  // Output: 6
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

In the example, the gcd function is tail-recursive. The recursive call to gcd is the last operation. This function also takes two parameters to compute the greatest common divisor.

Tail Recursion with Accumulators

You can use accumulators in tail-recursive functions. You can carry intermediate results through recursive calls.

Syntax

The syntax of tail-recursive function with an accumulator is -

@scala.annotation.tailrec
def functionName(param: Type, accumulator: AccType): ReturnType = {
   // base case
   if (condition) accumulator
   // recursive case
   else functionName(newParam, newAccumulator)
}

Example

Consider the example of tail recursion with an accumulator in Scala programming -

object Demo {
   @scala.annotation.tailrec
   def sum(n: Int, acc: Int = 0): Int = {
      if (n <= 0) acc
         else sum(n - 1, acc + n)
   }

   def main(args: Array[String]): Unit = {
      println(sum(5)) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

In the example, the sum function is tail-recursive. The recursive call to sum is the last operation. The function uses an accumulator to carry the intermediate sum through the recursive calls.

Tail Recursion with Nested Functions

You can combine Tail recursion with nested functions. It encapsulates the recursive logic within a helper function. It enhances code organization and readability.

Syntax

The syntax of tail-recursive function with nested functions is -

def outerFunction(params: Type): ReturnType = {
   @scala.annotation.tailrec
   def innerFunction(innerParams: Type, accumulator: AccType): ReturnType = {
      // base case
      if (condition) accumulator
      // recursive case
      else innerFunction(newInnerParams, newAccumulator)
   }

   innerFunction(initialInnerParams, initialAccumulator)
}

Example

Consider the example of tail recursion with nested functions in Scala programming -

object Demo {
   def fibonacci(n: Int): Int = {
      @scala.annotation.tailrec
      def fibHelper(a: Int, b: Int, count: Int): Int = {
         if (count == 0) a
            else fibHelper(b, a + b, count - 1)
      }

      fibHelper(0, 1, n)
   }

   def main(args: Array[String]): Unit = {
      println(fibonacci(10))  
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

In the example, the fibonacci function uses a nested helper function fibHelper. It performs tail-recursive computation of the Fibonacci sequence.

Tail Recursion with Collections

Tail recursion can be effectively used to process collections, like lists. It iterates through the elements recursively.

Syntax

The syntax of tail-recursive function to process collections is -

@scala.annotation.tailrec
def functionName(collection: List[Type], accumulator: AccType): ReturnType = {
   // base case
   if (collection.isEmpty) accumulator
   // recursive case
   else functionName(collection.tail, newAccumulator)
}

Example

Consider the example of tail recursion to sum the elements of a list in Scala programming -

object Demo {
   @scala.annotation.tailrec
   def sumList(list: List[Int], acc: Int = 0): Int = {
      if (list.isEmpty) acc
      else sumList(list.tail, acc + list.head)
   }

   def main(args: Array[String]): Unit = {
      println(sumList(List(1, 2, 3, 4, 5))) 
   }
}

Save the above program in Demo.scala. Use the following commands to compile and execute this program.

Command

> scalac Demo.scala
> scala Demo

Output

In the example, the sumList function is tail-recursive. The recursive call to sumList is the last operation. The function processes list by summing its elements.

Tail Recursion Summary

Tail Recursion is recursion where the recursive call is the last operation in the function.
The Scala compiler optimizes tail-recursive functions by reusing the current stack frame and prevents stack overflow errors.
The disadvantages of tail-recursion are no benefits of using it. Because its equivalent iterative program does not need any extra stack to store function calls.
You can use tail recursion with multiple parameters, accumulators, nested functions, and collections for various operations.

Print Page