Recursive functions are functions that invoke themselves, with some sort of condition to stop the execution. In Kotlin, a recursive function maintains a stack but can be optimized with a tailrec modifier.
Let's look at an example, an implementation of a factorial function.
First, let's take a look at a typical imperative implementation, loops, and state change in the following code snippet:
fun factorial(n: Long): Long {
var result = 1L
for (i in 1..n) {
result *= i
}
return result
}
It's nothing fancy nor particularly elegant. Now, let's take a look at a recursive implementation, no loops, and no state change:
fun functionalFactorial(n: Long): Long {
fun go(n: Long, acc: Long): Long {
return if (n <= 0) {
acc
} else {
go(n - 1, n * acc)
}
}
return go(n, 1)
}
We use an internal recursive function; the go function calling itself until a condition is reached. As you can see, we're starting with the last n value and reducing it in each recursive iteration.
An optimized implementation is similar but with a tailrec modifier:
fun tailrecFactorial(n: Long): Long {
tailrec fun go(n: Long, acc: Long): Long {
return if (n <= 0) {
acc
} else {
go(n - 1, n * acc)
}
}
return go(n, 1)
}
To test which implementation is faster, we can write a poor's man profiler function:
fun executionTime(body: () -> Unit): Long {
val startTime = System.nanoTime()
body()
val endTime = System.nanoTime()
return endTime - startTime
}
For our purposes, the executionTime function is okay, but any serious production code should be profiled with a proper profiling tool, such as Java Microbenchmark Harness (JMH):
fun main(args: Array<String>) {
println("factorial :" + executionTime { factorial(20) })
println("functionalFactorial :" + executionTime { functionalFactorial(20) })
println("tailrecFactorial :" + executionTime { tailrecFactorial(20) })
}
Here's the output for the preceding code:
The tailrec optimized version is even faster than the normal imperative version. But tailrec isn't a magic incantation that will make your code run faster. As a general rule, the tailrec optimized code will run faster than the unoptimized version, but will not always beat a good old imperative code.
Let's explore a Fibonacci implementation, starting with an imperative one as follows:
fun fib(n: Long): Long {
return when (n) {
0L -> 0
1L -> 1
else -> {
var a = 0L
var b = 1L
var c = 0L
for (i in 2..n) {
c = a + b
a = b
b = c
}
c
}
}
}
Now, let's take a look at a functional recursive implementation:
fun functionalFib(n: Long): Long {
fun go(n: Long, prev: Long, cur: Long): Long {
return if (n == 0L) {
prev
} else {
go(n - 1, cur, prev + cur)
}
}
return go(n, 0, 1)
}
Now let's check with its corresponding tailrec version, as follows:
fun tailrecFib(n: Long): Long {
tailrec fun go(n: Long, prev: Long, cur: Long): Long {
return if (n == 0L) {
prev
} else {
go(n - 1, cur, prev + cur)
}
}
return go(n, 0, 1)
}
Then again, let's see its profiling with executionTime:
fun main(args: Array<String>) {
println("fib :" + executionTime { fib(93) })
println("functionalFib :" + executionTime { functionalFib(93) })
println("tailrecFib :" + executionTime { tailrecFib(93) })
}
The output will look something like the following:
The tailrec implementation is much faster than the recursive version, but not as fast as a normal imperative implementation.