Get Even More Visitors To Your Blog, Upgrade To A Business Listing >>

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


This post first appeared on Java Tutorial : Blog To Learn Java Programming, please read the originial post: here

Share the post

Kotlin: Tail recursive functions

×

Subscribe to Java Tutorial : Blog To Learn Java Programming

Get updates delivered right to your inbox!

Thank you for your subscription

×