Kotlin Recursion and Tail Recursion

In this article, you will learn to create recursive functions. A self-calling function. In addition, you will also learn about tail-recursive functions.

that calls itselfFunctionIt is called a recursive function. And, this technique is called recursion.

A physical world example is to place two parallel mirrors opposite each other. Any object between them will be recursively reflected.

How does recursion work in programming?

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

In this case, the recurse() function is called from within the body of the recurse() function itself. The working principle of this program is as follows:

In this case, the recursive call will continue indefinitely, leading to infinite recursion.

To avoid infinite recursion, you can use recursion in one branch while not using recursion in the other branches.if ... else(or similar methods).

Example: Using recursion to find the factorial of a number

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

When running this program, the output is:

4　Factorial =　24

How does this program work?

The following diagram of factorial() illustrates the recursive calls made by the function:

The steps involved are as follows:

factorial(4)　　　　　　　　　　　　　　//　The1The next function call, parameters:　4
4*factorial(3)　　　　　　　　　　　　//　The2The next function call, parameters:　3
4*(3*factorial(2))　　　　　　　　//　The3The next function call, parameters:　2
4*(3*(2*factorial(1))　　　　//　The4The next function call, parameters:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Kotlin tail recursion

Tail recursion is not a feature of the Kotlin language, but a general concept. Some programming languages, including Kotlin, use it to optimize recursive calls, while others (such as Python) do not support them.

What is tail recursion?

In ordinary recursion, all recursive calls are executed first, and then the result is calculated based on the return values (as shown in the above example). Therefore, you will not get the result before all recursive calls are made.

In tail recursion, the computation is first executed, followed by the recursive call (the recursive call passes the current step's result to the next recursive call). This makes the recursive call equivalent to a loop and avoids the risk of stack overflow.

Tail recursion conditions

If the function call to itself is the last operation it performs, then the recursive function can perform tail recursion. For example,

Example1:does not meet the tail recursion condition because the function call to itself n*factorial(n-1) is not the final operation.

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

Example2:meets the tail recursion condition because the function call fibonacci(n-1, a+b, a) is the final operation.

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

To tell the compiler to perform tail recursion in Kotlin, you need to mark the function with the 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)
}

When running this program, the output is:

354224848179261915075

This program calculates the nth term of the Fibonacci sequence:100th term. Since the output can be a very large integer, we import the BigInteger class from the Java standard library.

In this case, the function fibonacci() is marked with the trarec modifier, making it eligible for tail recursion optimization. Therefore, the compiler optimizes the recursion in this situation.

If you try to find the nth term of the Fibonacci sequence without using tail recursion,20000th term (or any other large integer), the compiler will throw a java.lang.StackOverflowError exception.
However, our program above runs well. This is because we used tail recursion, which uses an efficient loop-based version instead of traditional recursion.

Example: Factorial using tail recursion

The example (the first example) above, which is used to calculate the factorial of a number, cannot be optimized for tail recursion. This is another program that performs the same task.

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

When running this program, the output is:

5　Factorial=　120

The compiler can optimize recursion in this program because the recursive function can perform tail recursion, and we use the tailrec modifier to tell the compiler to optimize recursion.