Post
Ask Question

Inspecting Tail Recursion

Introduction

In the article, we will inspect tail recursion, we will understand the concept pragmatically by deep-diving into some of the examples. For understanding purposes, I am using Scala-based examples and exploring the @tailrec annotation, how the compiler treats the program differently which are marked with @tailrec annotation, and the benefits of tail recursion, let’s explore.

Tail Recursion

A function is tail-recursive when the function calls itself at the very end of the program after all the calculations within the program are done and then the function invokes itself.

Remember function call is the last thing in the function.

Let’s understand by the example, first with a standard recursive function. Let’s add the elements of the Integers List recursively.

#1. Add the elements of the List, size of the List is 5.

object MyClass {
    def add(list: List[Int]): Int = list match {
        case Nil => 0
        case x::tail => x + add(tail)
    }
    def main(args: Array[String]) {
        print(add(List.range(1, 5)));
    }
}

Output: 10, remember 5 is exclusive that’s why the output is 10.

#2. Execute the same program, now the list size is 10000.

object MyClass {
    def add(list: List[Int]): Int = list match {
        case Nil => 0
        case x::tail => x + add(tail)
    }
    def main(args: Array[String]) {
        print(add(List.range(1, 10000)));
    }
}

Output: Exception in thread "main" java.lang.StackOverflowError

at Main$.add(jdoodle.scala:6)

at Main$.add(jdoodle.scala:7)

this is the standard recursive function, the program may give the impression that function call ‘add’ is happening at the very end, but it’s not.

case x :: tail => x + add(tail)

First add(tail) method is evaluated then the result is added to x, which means there are 2 steps, first invocation of add then addition, that’s why add(tail) is not the last thing happening in the program and it’s not tail-recursive.

# Add the elements of the list where the size of the list is 10000, tail recursively.

object MyClass {
    def add(list: List[Int]): Int = {
        def addHelper(list: List[Int], accumulator: Int): Int = {
            list match {
                case Nil => accumulator
                case x::tail => addHelper(tail, accumulator + x)
            }
        }
        addHelper(list, 0)
    }
    def main(args: Array[String]) {
        print(add(List.range(1, 10000)));
    }
}

Output: 49995000

The above program is a tail-recursive program because addHelper is calling itself at the very end and there are no computations after it and the summation of list elements are taken care of within the function.

What is so special with the approach of calling the function at the end

In the 'addHelper' function we are storing the sum at every recursive call and once the function call is over the sum value is returned directly, since no other computation is happening after the function, the memory references of the previous function call is not required and that’s why the tail-recursive programs have smaller memory footprints.

Understanding the @tailrec annotation

@tailrec is a very smart annotation, if the function is marked with this annotation, then annotation verifies whether the function is tail call optimized or not.

Considering our 1st program where the size of the list is 5, and we marked our function now with @tailrec annotation

import scala.annotation.tailrec
object MyClass {
    @tailrec
    def add(list: List[Int]): Int = list match {
        case Nil => 0
        case x::tail => x + add(tail)
    }
    def main(args: Array[String]) {
        print(add(List.range(1, 5)));
    }
}

Output: jdoodle.scala:6: error: could not optimize @tailrec annotated method add: it contains a recursive call, not in tail position

Although the size of the list is only 5, the compiler issues an error and confirms that the method is not tail call optimized.

And with our 2nd implementation the program which was tail recursive, the compiler never issues a warning, and the execution is successful.

import scala.annotation.tailrec
object MyClass {
    def add(list: List[Int]): Int = {
        @tailrec
        def addHelper(list: List[Int], accumulator: Int): Int = {
            list match {
                case Nil => accumulator
                case x::tail => addHelper(tail, accumulator + x)
            }
        }
        addHelper(list, 0)
    }
    def main(args: Array[String]) {
        print(add(List.range(1, 10000)));
    }
}

If we move the @tailrec annotation to the ‘add’ method compiler will again issue an error as the ‘add’ method is not tail-recursive.


Similar Articles