Kotlin Recursion and Tail Recursion with examples

A function is called recursive function if it calls itself and this process is called recursion.

How a recursive function looks like?

Here the function myfunction() calls itself, this is a recursive function.

fun myfunction(){    
  //some code  
  ....
  //myfunction() calling myfunction()
  myfunction()   
}

Lets take an example to understand the recursion.

Kotlin Recursion example

This is a simple example of factorial. Here we have defined a function fact() to calculate the factorial of a number that it passed to this function as a parameter. In the function body we are calling this function again, this process is called recursion.

User is asked to enter a positive integer number and based on the input, program finds the factorial of the input number by passing the input number as an argument to the user defined function fact().

fun main(args: Array<String>) {
    print("Enter a positive integer number: ")
    val number: Int =Integer.valueOf(readLine())
    val factorial = fact(number)
    println("Factorial of $number = $factorial")
}

//recursive function
fun fact(num: Int): Int {
    return if(num == 1){
        num
    }
    else{
        //function fact() calling itself
        num*fact(num-1)
    }
}

Output:

Tail Recursion

In recursion the computation is done after the recursive call, the example of factorial we have seen above is an example of recursion or head recursion where to calculate the factorial of n we need the factorial of n-1.

In Tail recursion the computation is done at the beginning before the recursive call. In tail recursion the call to the recursive function occurs at the end of the function. Which means the computation is done first and then passed to the next recursive call.

Lets take an example of tail recursion.

Tail Recursion Example

To declare a tail recursive function we use tailrec modifier before the function.

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

tailrec fun fact(n: Int, temp: Int = 1): Int {
    return if (n == 1){
        temp
    } else {
        fact(n-1, temp*n)
    }
}

Output: