Kotlin: Tail recursive functions

In this post, I am going to explain about the concept called tail recursion. This is a new concept, used to build recursive functions effectively in functional programming languages. Most of the people think that recursion is inefficient, but that is not true. The efficiency of recursion is depending on the way you code it.

Below snippet calculates the factorial of a number.

fun fact(n: Int): Int {

         if (n == 0) return 1

         return n * fact(n - 1)

}

Programming languages maintain stack frames to keep track of recursive calls. Following step-by-step procedure explains that.

Step 1: fact(5) = 5 * fact(5-1) = 5 * fact (4)

Step 2: fact(4) = 4 * fact(3), to get the result of fact(4), we need to calculate fact(3) first.

Step 3: fact(3) = 3 * fact(2), to get the result of fact(3), we need to calculate fact(2) first.

Step 4: fact(2) = 2 * fact(1), to get the result of fact(2), we need to calculate fact(1) first.

Step 5: fact(1) = 1 * fact(0), to get the result of fact(1), we need to calculate fact(0) first.

Finally, we reached our base condition, fact(0) = 1.

fact(1) = 1 * fact(0) =  1 * 1 = 1

fact(2) = 2 * fact(1) =  2 * 1 = 2

fact(3) = 3 * fact(2) =  3 * 2 = 6

fact(4) = 4 * fact(3) =  4 * 6 = 24

fact(5) = 5 * fact(4) =  5 * 24 = 120

To calculate fact(5), We require 5 stack frames, So to calculate fact(1000000), we require 1000000 stack frames. Since stack is limited in size, you will end up in stack overflow error for large values, and also it impacts performance for large values.

How tail recursion helps in this scenario?

When you define a function as tail recursive function, compiler optimizes the recursion.

How to define a tail recursive function?

By using tailrec modifier, you can define a tail recursive function. To make a function tail recursive, it should meet one precondition. The function must call itself as the last operation it performs.

We can rewrite the factorial function like below.

tailrec fun fact(n: Int, accum: Int = 1): Int{

         var soFar = n * accum

    return if (n <= 1) {

        soFar

    } else {

        fact(n - 1, soFar)

    }

}

When you ran above function, kotlin optimizes the recursive function and it replaces the stack frame with last result.

fact(5) = fact(4, 5*1)

                 = fact(3, 5*4)

                 = fact(2, 20*3)

                 = fact(1, 60*2)

                 = 120

Previous                                                 Next                                                 Home