Recursion

Recursion is the programming technique of calling a function within that same function. Tail recursion is an optimization that can be explicitly applied to some recursive functions.

A recursive function uses the result of the previous recursive call. Factorials are a common example—factorial(n) multiplies all numbers from 1 to n, and can be defined like this:

• factorial(1) is 1
• factorial(n) is n * factorial(n - 1)

factorial() is recursive because it uses the result from the same function applied to its modified argument. Here’s a recursive implementation of factorial():

// Recursion/Factorial.kt
package recursion
import atomictest.eq

fun factorial(n: Long): Long {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

fun main() {
  factorial(5) eq 120
  factorial(17) eq 355687428096000
}

While this is easy to read, it’s expensive. When calling a function, the information about that function and its arguments are stored in a call stack. You see the call stack when an exception is thrown and Kotlin displays the stack trace:

// Recursion/CallStack.kt
package recursion

fun illegalState() {
  // throw IllegalStateException()
}

fun fail() = illegalState()

fun main() {
  fail()
}

If you uncomment the line containing the exception, you’ll see the following:

Exception in thread "main" java.lang.IllegalStateException
  at recursion.CallStackKt.illegalState(CallStack.kt:5)
  at recursion.CallStackKt.fail(CallStack.kt:8)
  at recursion.CallStackKt.main(CallStack.kt:11)

The stack trace displays the state of the call stack at the moment the exception is thrown. For CallStack.kt, the call stack consists of only three functions:

The Call Stack

We start in main(), which calls fail(). The fail() call is added to the call stack along with its arguments. Next, fail() calls illegalState(), which is also added to the call stack.

When you call a recursive function, each recursive invocation adds a frame to the call stack. This can easily produce a StackOverflowError, which means that your call stack became too large and exhausted the available memory.

Programmers commonly cause StackOverflowErrors by forgetting to terminate the chain of recursive calls—this is infinite recursion:

// Recursion/InfiniteRecursion.kt
package recursion

fun recurse(i: Int): Int = recurse(i + 1)

fun main() {
  // println(recurse(1))
}

If you uncomment the line in main(), you’ll see a stacktrace with many duplicate calls:

Exception in thread "main" java.lang.StackOverflowError
at recursion.InfiniteRecursionKt.recurse(InfiniteRecursion.kt:4)
at recursion.InfiniteRecursionKt.recurse(InfiniteRecursion.kt:4)
...
at recursion.InfiniteRecursionKt.recurse(InfiniteRecursion.kt:4)

The recursive function keeps calling itself (with a different argument each time), and fills up the call stack:

Infinite Recursion

Infinite recursion always ends with a StackOverflowError, but you can produce the same result without infinite recursion, simply by making enough recursive function calls. For example, let’s sum the integers up to a given number, recursively defining sum(n) as n + sum(n - 1):

// Recursion/RecursionLimits.kt
package recursion
import atomictest.eq

fun sum(n: Long): Long {
  if (n == 0L) return 0
  return n + sum(n - 1)
}

fun main() {
  sum(2) eq 3
  sum(1000) eq 500500
  // sum(100_000) eq 500050000       // [1]
  (1..100_000L).sum() eq 5000050000  // [2]
}

This recursion quickly becomes expensive. If you uncomment line [1], you’ll discover that it takes far too long to complete, and all those recursive calls overflow the stack. If sum(100_000) still works on your machine, try a bigger number.

Calling sum(100_000) causes a StackOverflowError by adding 100_000 sum() function calls to the call stack. For comparison, line [2] uses the sum() library function to add the numbers within the range, and this does not fail.

To avoid a StackOverflowError, you can use an iterative solution instead of recursion:

// Recursion/Iteration.kt
package iteration
import atomictest.eq

fun sum(n: Long): Long {
  var accumulator = 0L
  for (i in 1..n) {
    accumulator += i
  }
  return accumulator
}

fun main() {
  sum(10000) eq 50005000
  sum(100000) eq 5000050000
}

There’s no risk of a StackOverflowError because we only make a single sum() call and the result is calculated in a for loop. Although the iterative solution is straightforward, it must use the mutable state variable accumulator to store the changing value, and functional programming attempts to avoid mutation.

To prevent call stack overflows, functional languages (including Kotlin) use a technique called tail recursion. The goal of tail recursion is to reduce the size of the call stack. In the sum() example, the call stack becomes a single function call, just as it did in Iteration.kt:

Regular Recursion vs. Tail Recursion

To produce tail recursion, use the tailrec keyword. Under the right conditions, this converts recursive calls into iteration, eliminating call-stack overhead. This is a compiler optimization, but it won’t work for just any recursive call.

To use tailrec successfully, recursion must be the final operation, which means there can be no extra calculations on the result of the recursive call before it is returned. For example, if we simply put tailrec before the fun for sum() in RecursionLimits.kt, Kotlin produces the following warning messages:

• A function is marked as tail-recursive but no tail calls are found
• Recursive call is not a tail call

The problem is that n is combined with the result of the recursive sum() call before returning that result. For tailrec to be successful, the result of the recursive call must be returned without doing anything to it during the return. This often requires some work in rearranging the function. For sum(), a successful tailrec looks like this:

// Recursion/TailRecursiveSum.kt
package tailrecursion
import atomictest.eq

private tailrec fun sum(
  n: Long,
  accumulator: Long
): Long =
  if (n == 0L) accumulator
  else sum(n - 1, accumulator + n)

fun sum(n: Long) = sum(n, 0)

fun main() {
  sum(2) eq 3
  sum(10000) eq 50005000
  sum(100000) eq 5000050000
}

By including the accumulator parameter, the addition happens during the recursive call and you don’t do anything to the result except return it. The tailrec keyword is now successful, because the code was rewritten to delegate all activities to the recursive call. In addition, accumulator becomes an immutable value, eliminating the complaint we had for Iteration.kt.

factorial() is a common example for demonstrating tail recursion, and is one of the exercises for this atom. Another example is the Fibonacci sequence, where each new Fibonacci number is the sum of the previous two. The first two numbers are 0 and 1, which produces the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... This can be expressed recursively:

// Recursion/VerySlowFibonacci.kt
package slowfibonacci
import atomictest.eq

fun fibonacci(n: Long): Long {
  return when (n) {
    0L -> 0
    1L -> 1
    else ->
      fibonacci(n - 1) + fibonacci(n - 2)
  }
}

fun main() {
  fibonacci(0) eq 0
  fibonacci(22) eq 17711
  // Very time-consuming:
  // fibonacci(50) eq 12586269025
}

This implementation is terribly inefficient because the previously-calculated results are not reused. Thus, the number of operations grows exponentially:

Inefficient Computation of Fibonacci Numbers

When computing the 50th Fibonacci number, we first compute the 49th and 48th numbers independently, which means we compute the 48th number twice. The 46th number is computed as many as 4 times, and so on.

Using tail recursion, the calculations become dramatically more efficient:

// Recursion/Fibonacci.kt
package recursion
import atomictest.eq

fun fibonacci(n: Int): Long {
  tailrec fun fibonacci(
    n: Int,
    current: Long,
    next: Long
  ): Long {
    if (n == 0) return current
    return fibonacci(
      n - 1, next, current + next)
  }
  return fibonacci(n, 0L, 1L)
}

fun main() {
  (0..8).map { fibonacci(it) } eq
    "[0, 1, 1, 2, 3, 5, 8, 13, 21]"
  fibonacci(22) eq 17711
  fibonacci(50) eq 12586269025
}

We could avoid the local fibonacci() function using default arguments. However, default arguments imply that the user can put other values in those defaults, which produce incorrect results. Because the auxiliary fibonacci() function is a local function, we don’t expose the additional parameters, and you can only call fibonacci(n).

main() shows the first eight elements of the Fibonacci sequence, the result for 22, and finally the 50th Fibonacci number that is now produced very quickly.

Exercises and solutions can be found at www.AtomicKotlin.com.