Recursive functions

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.