Function - Recursion and Tail Recursion

Recursion function

 is a function that calls itself continuously. This technique is called recursion,

Tail recursion

is a recursion that performs the calculation first, then makes the recursive call. The result of the current step is passed into the next recursive call.

Example: Find the factorial of a Number using Recursion

fun main(args: Array<String>) {
    val number = 4
    val result: Long

    result = factorial(number)
    println("Factorial of $number = $result")
}

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

How this program works?

Here are the steps involved:

factorial(4)              // st function call. Argument: 4
4*factorial(3)            // nd function call. Argument: 3
4*(3*factorial(2))        // rd function call. Argument: 2
4*(3*(2*factorial(1)))    // th function call. Argument: 1 
4*(3*(2*1))                 
24

Tail recursion

is a recursion that performs the calculation first, then makes the recursive call. The result of the current step is passed into the next recursive call.

The recursive call must be the last call of the method.

To tell the compiler to perform tail recursion in Kotlin, you need to mark the function with tailrec modifier.

fun main(args: Array<String>) {  
    val number = 4  
    val result: Long  
    result = factorial(number)  
    println("Factorial of $number = $result")  
}  
  
tailrec fun factorial(n: Int, run: Int = 1): Long {  
    return if (n == 1){  
        run.toLong()  
    } else {  
        factorial(n-1, run*n)  
    }  
}  
Output:
Factorial of 4 = 24