In this tutorial, we will learn about kotlin recursive function, kotlin tail recursive function. We will learn what a tail recursive function is, how to use this tail recursive function in a kotlin program etc.

At first, let’s see what a recursive function is.

Recursive function in Kotlin

A recursive function in kotlin is function that call itself. For example,

fun printHello() {
   println("Hello")
   printHello();
}

Here, printHello() function calls itself. So, printHello() function is recursive function.

Another Example –

fun main(args: Array<String>) {
   val product = findSum(5);
   print("Sum = $product")
}

fun findSum(num: Int): Int {
   return if (num == 1) num else num + findSum(num - 1)
}

When you run the program, you will get output as shown below –
Sum = 15

Let’s understand step by step how does the above program works?
In the above program, main function calls a function findSum() that find the sum of n natural numbers. So, when you pass 100 as a parameter to the function, it will return 5050. Now, see the code inside findSum() function. It uses recursion i.e. findSum() function is calling itself.

For value 5, the function calls will be like –

findSum(5)                        // 1st call to the function with argument 5
5 + findSum(4)                  // 2nd call to the function with argument 4
5 + (4 + findSum(3))            // 3rd call to the function with argument 3
5 + (4 + (3 + findSum(2)))      // 4th call to the function with argument 2
5 + (4 + (3 + (2 + findSum(1))))  // 5th call to the function with argument 1
5 + (4 + (3 + (2 + 1)))	// calculations are done in 5th function call..
5 + (4 + (3 + 3))		// Back to 4th function call, calculations are done
5 + (4 + 6)		// Back to 3rd function call, calculations are done
5 + 10			// Back to 2nd function call, calculations are done
15			// Back to 1st function call, calculations are done and result is returned

Notice that functions are being called first and calculations are being done in last step. So, compiler stores data of each function call in memory (i.e. stack)

This is drawback of normal recursion of function. What if you have to get sum of larger value e.g. for value = 999999. Calling function in this way will surely result in stackoverflow error. Imagine number of times this function will be called. Then, multiply it with the amount of space this function needs in memory to maintain each function call. Now, You have an idea why stackoverflow occurs.

Now, how to deal with it? How can you calculate sum of such large number?

Then answer is – Use Tail Recursion in function.

What is Tail Recursion in Kotlin

Tail recursion is a technique to recursively call a function in which calculations are done first, then function is called.

In this technique, we do partial calculation with each step. In the final step, we get output.

A recursive function call is tail recursion if calculations are performed first, then, function calls itself. It means, function call is the last thing executed by the function in tail recursion. Such function is kotlin tail recursive function.

What is the benefit of using tail recursion in kotlin ?

In kotlin tail recursive function call, function call is the last thing executed by the function. There is nothing left to do in the current function. So, there is of no use to save current function stack in memory. This is the catch in tail recursion. Since current function stack is of no use once next function is called, compiler re-use current function stack for next function call. That’s why we do not see stackoverflow error. We reuse the current function frame for next function in each successive function call.

Let’s analyse above program using tail recursion in kotlin.

We can write above program using tail recursion as below –

fun main(args: Array<String>) {
   val product = findSum(5);
   print("Sum = $product")
}

tailrec fun findSum(num: Int, stepTotal: Long = 0): Long {
   return if (num == 0) stepTotal else findSum(num - 1, stepTotal + num)
}

We have already seen how this function works in normal function call. Let’s see this using tail recursion in kotlin

function findSum() calls using tail recursion in kotlin as below –

findSum(5, 0)		// 1st function call, called by main function.
findSum(4, 5)		// 2nd function call, perform partial calculation as well
findSum(3, 9)		// 3rd function call, perform partial calculation as well
findSum(2, 12)		// 4th function call, perform partial calculation as well
findSum(1, 14)		// 5th function call, perform partial calculation as well
findSum(0, 15)		// 6th function call, perform partial calculation as well
15			// Got the result, return to main function.

Note that there is no callback to caller function. This is because compiler optimises the program for tail recursion and reuse the current function frame in next function call. Since, current function gets calculations performed in previous function call, it calculates value and makes next function call. Thus, partial calculations are done in each step.

Thus, Compiler use tail recursion technique to overcome memory issue in recursive function call.

Now, how will you use tail recursion in function in kotlin? What are criteria to use it in kotlin ? etc.

How to use tail recursion in Kotlin

Below are the main criteria to use tail recursion in kotin –
A. Function call must be the last thing to execute in the function.
B. Function must be marked with tailrec to tell the compiler to optimise the function call for tail recursion.

For example,

fun main(args: Array<String>) {
   val product = findProduct(8);
   print("Product = $product")
}

tailrec fun findProduct(num: Int, stepTotal: Long = 1): Long {
   return if (num == 0) stepTotal else findProduct(num - 1, stepTotal * num)
}

When you run the above program, you will get below output –
Product = 40320

Here, findProduct() is kotlin tail recursive function.

Notice that function findProduct() meets all the above criteria for tail recursion in kotlin. So, compiler will use tail recursion technique and optimise the function call.

Exercises on Kotlin Tail Recursive Function

fun main(args: Array<String>) {
   val sum = findSum(999999999);
   print("Sum = $sum")
}

fun findSum(num: Int, stepTotal: Long = 0): Long {
   return if (num == 0) stepTotal else findSum(num - 1, stepTotal + num)
}

fun main(args: Array<String>) {
   val sum = findSum(999999999);
   print("Sum = $sum")
}

tailrec fun findSum(num: Int, stepTotal: Long = 0): Long {
   return if (num == 0) stepTotal else findSum(num - 1, stepTotal + num)
}

fun main(args: Array<String>) {
   val sum = findSum(999999999);
   print("Sum = $sum")
}

tailrec fun findSum(num: Int): Int {
   return if (num == 1) num else num + findSum(num - 1)
}

fun main(args: Array<String>) {
   val numb = 6
   println("Factorial of $numb = ${factorial(numb)}")
}

tailrec fun factorial(n: Int, run: Int = 1): Long {
   return if (n == 1) run.toLong() else factorial(n - 1, run * n)
}

That’s end of tutorial on Kotlin Tail Recursive Function.