Recursion is a powerful concept in programming that allows functions to call themselves to solve problems. However, recursive functions can sometimes lead to stack overflow errors if they have deep recursion levels.

Kotlin provides the tailrec modifier to optimize recursive functions and convert them into an efficient iterative version under the hood. This helps in reducing memory consumption and avoiding stack overflow errors.

In this post, we’ll explore how Kotlin’s tailrec modifier works, when to use it, and see examples with explanations.

Understanding tailrec modifier, Recursive Functions and Tail Recursive Function

A recursive function is one that calls itself to solve a problem by breaking it down into smaller instances. While recursion provides an elegant solution, deep recursion can lead to excessive memory usage due to function call stack frames.

A tail-recursive function is a special type of recursive function where the recursive call is the last operation before returning a result. This allows the compiler to optimize it into a loop, eliminating the need for additional stack frames and improving efficiency.

In Kotlin, recursive functions are fully supported, and the tailrec modifier can be used to optimize tail-recursive functions. Let’s explore these concepts with examples of factorial and Fibonacci calculations.

Factorial Function

Imperative Implementation

fun factorial(n: Long): Long {
    var result = 1L
    for (i in 1..n) {
        result *= i
    }
    return result
}

This is a straightforward imperative implementation of the factorial function using a for loop to calculate the factorial of a given number n.

Recursive Implementation

fun functionalFactorial(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)
}

In the recursive version, we use an internal recursive function go that calls itself until a base condition (n <= 0) is reached. The accumulator (acc) is multiplied by n at each recursive step.

Tail-Recursive Implementation

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)
}

The tail-recursive version is similar to the recursive one, but with the addition of the tailrec modifier. This modifier informs the compiler that the recursion is tail-recursive, allowing for optimization.

Fibonacci Function

Imperative Implementation

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
        }
    }
}

This is a typical imperative implementation of the Fibonacci function using a for loop to iteratively calculate Fibonacci numbers.

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)
}

The recursive version uses an internal function go that recursively calculates Fibonacci numbers. The function maintains two previous values (prev and cur) during each recursive call.

Tail-Recursive Implementation

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)
}

The tail-recursive version of the Fibonacci function, similar to the recursive one, benefits from the tailrec modifier for potential optimization.

Profiling with executionTime:

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
}

fun main(args: Array<String>) {
    println("factorial: " + executionTime { factorial(20) })
    println("functionalFactorial: " + executionTime { functionalFactorial(20) })
    println("tailrecFactorial: " + executionTime { tailrecFactorial(20) })

    println("fib: " + executionTime { fib(93) })
    println("functionalFib: " + executionTime { functionalFib(93) })
    println("tailrecFib: " + executionTime { tailrecFib(93) })
}

This main function tests the execution time of each implementation using the executionTime function. It helps compare the performance of the imperative, recursive, and tail-recursive versions of both factorial and Fibonacci functions.

These execution times represent the time taken to run each function, providing insights into their relative performance. Please note that actual execution times may vary based on the specific environment and hardware.

The output of the profiling demonstrates that tail-recursive implementations, indicated by the tailrec modifier, are generally more optimized and faster than their purely recursive counterparts. However, it’s essential to note that tail recursion doesn’t automatically make the code faster in all cases, and imperative implementations might still outperform recursive ones. The choice between recursion and tail recursion depends on the specific use case and the characteristics of the problem being solved.