Kotlin Recursion (Recursive Function) and Tail Recursion

Kotlin recursion: In this tutorial, you will learn to create recursive functions; a function that calls itself. Likewise, you will learn about tail-recursive functions.

Recursion is the process where a function calls itself, and the function which calls itself is know as recursive function.

A function that calls itself is known as recursive function. What’s more, this method is known as recursion.

A physical world example is place two equal mirrors confronting one another. Any object in the middle of them would be reflected recursively.

---

How does recursion work in programming?

fun main(args: Array<String>) {
    ... .. ...
    recurse()
    ... .. ...
}

fun recurse() {
    ... .. ...
    recurse()
    ... .. ...
}

Here, the recurse() work is called from the body of recurse() work itself. Here’s the way this program works:

• 

Here, the recursive call proceeds always causing infinite recursion.

To avoid infinite recursion, if…else (or comparable methodology) can be used where one branch settles on the recursive call and the other doesn’t.

---

Example: Find 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)
}

When you run the program, the output will be:

Factorial of 4 = 24

---

How this program function?

The recursive call of the factorial() function can be clarified in the accompanying figure:

• 

Here are the steps involved:

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

---

Kotlin Tail Recursion

Tail recursion is a generic concept instead of the component of the Kotlin language. Some programming languages including Kotlin use it to enhance recursive calls, though different languages (eg. Python) don’t support them.

---

What is tail recursion?

In typical recursion, you play out all recursive calls first, and calculate the outcome from return values finally (as shown in the above example). Consequently, you don’t get results until all recursive calls are made.

In tail recursion, calculations are performed first, at that point recursive calls are executed (the recursive consider passes the result of your present step to the next recursive call). This settles on the recursive decision comparable to looping, and stays away from the danger of stack overflow.

---

Condition for tail recursion

A recursive function is eligible for tail recursion if the function call to itself is the last activity it performs. For instance,

Example 1: Not eligible for tail recursion on the grounds that the function call to itself n*factorial(n-1) isn’t the last activity.

fun factorial(n: Int): Long {

    if (n == 1) {
        return n.toLong()
    } else {
        return n*factorial(n - 1)     
    }
}

Example 2: Eligible for tail recursion since work call to itself fibonacci(n-1, a+b, a) is the last activity.

fun fibonacci(n: Int, a: Long, b: Long): Long {
    return if (n == 0) b else fibonacci(n-1, a+b, a)
}

---

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

---

Example: Tail Recursion

import java.math.BigInteger

fun main(args: Array<String>) {
    val n = 100
    val first = BigInteger("0")
    val second = BigInteger("1")

    println(fibonacci(n, first, second))
}

tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
    return if (n == 0) a else fibonacci(n-1, b, a+b)
}

At the point when you run the program, the output will be:

354224848179261915075

This program computes the 100^th term of the Fibonacci arrangement. Since the output can be an exceptionally huge integer, we have imported BigInteger class from Java standard library.

Here, the function fibonacci() is set apart with tailrec modifier and the function is eligible for tail-recursive call. Thus, the compiler optimizes the recursion for this situation.

---

On the off chance that you attempt to track down the 20000^th term (or some other enormous integer) of the Fibonacci arrangement without using tail recursion, the compiler will throw java.lang.StackOverflowError exception. In any case, our program above works just fine. This is on the grounds that we have used tail recursion which uses effective loop based form rather than customary recursion.

---

Example: Factorial Using Tail Recursion

The example to compute the factorial of a number in the above example (first example) can’t be improved for tail recursion. Here’s an alternate program to play out a similar assignment.

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

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

At the point when you run the program, the output will be:

Factorial of 5 = 120

The compiler can enhance the recursion in this program as the recursive function is eligible for tail recursion, and we have used tailrec modifier that tells the compiler to optimize the recursion.

---

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.

Kotlin Functions