4 Recursion, corecursion, and memoization

This chapter explains how to think and program with recursion and corecursion in Kotlin, and why the language’s tail call elimination makes corecursive (tail-recursive) solutions both expressive and safe. It contrasts recursive processes that defer work and consume stack space with corecursive ones that evaluate each step immediately and can be compiled to loops when marked tailrec. The chapter shows how to turn intuitive but stack-unsafe recursive definitions into tail-recursive implementations by introducing helper functions, accumulators, and local functions, and it emphasizes choosing corecursion whenever possible to avoid stack overflows while preserving clarity and intent.

Building on that foundation, the chapter develops a toolkit of list-processing patterns. It starts from head/tail decomposition and progressively abstracts toward reusable folds: foldLeft (corecursive and stack-safe) and foldRight (naturally recursive and potentially unsafe). With these, it refactors common tasks—summing lists, joining elements into strings, reversing lists, mapping—into concise, reusable combinators. It also demonstrates how to transform loop-based flows into functional constructs such as range, unfold, and iterate, and turns the naive, exponential Fibonacci into a fast, tail-recursive BigInteger version. Along the way, it highlights the difference between strict list processing and the laziness of control structures, noting that truly lazy collections arrive later in the book.

The chapter closes with memoization as a complementary optimization: caching results to avoid recomputation. It shows implicit memoization (building intermediate lists you can reuse) and explicit memoization via maps, then generalizes with a thread-safe Memoizer that turns any single-argument function into a memoized one. It extends the approach to multi-argument functions via currying or tuples, discusses purity (memoized functions remain extensionally pure; only time varies), and warns about practical concerns such as memory growth and when to consider weak/soft references. Combined with tail recursion, folds, and unfold/iterate patterns, memoization provides a pragmatic path to safe, expressive, and efficient functional Kotlin.

Figure 4.1. Corecursively transforming a list of characters into a string

Figure 4.2. Recursively transforming a list of characters into a string

Figure 4.3. A corecursive computation

Figure 4.4. A recursive computation

Figure 4.5. A flow chart of the imperative computation of the sum of n first integers

• A recursive function calls itself, using this call to itself as an element for further computation.
  
• Recursive functions push the current computation state onto the stack before recursively calling themselves.
  
• The Kotlin default stack size is limited. If the number of recursive steps is too high, you’ll get a StackOverflowException.
  
• Tail-recursive functions are functions in which the recursive call is in the last (tail) position.
  
• In Kotlin, tail-recursive functions are optimized using Tail Call Elimination (TCE).
  
• Lambdas can be made recursive.
  
• Memoization allows functions to remember their computed result in order to speed up later access.
  
• Memoization can be made automatic.
  

FAQ

tailrec fun sumTail(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sumTail(n - 1, acc + n)

fun sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

fun sum(n: Int): Int {
  tailrec fun go(i: Int, acc: Int): Int =
    if (i == 0) acc else go(i - 1, acc + i)
  return go(n, 0)
}

fun sum(list: List<Int>): Int {
  tailrec fun go(xs: List<Int>, acc: Int): Int =
    if (xs.isEmpty()) acc else go(xs.drop(1), acc + xs.first())
  return go(list, 0)
}

fun <T, U> foldLeft(xs: List<T>, z: U, f: (U, T) -> U): U {
  tailrec fun go(ys: List<T>, acc: U): U =
    if (ys.isEmpty()) acc else go(ys.drop(1), f(acc, ys.first()))
  return go(xs, z)
}

fun range(s: Int, e: Int) = unfold(s, { it + 1 }, { it < e })
fun <T> unfold(seed: T, f: (T)->T, p: (T)->Boolean): List<T> {
  tailrec fun go(acc: List<T>, x: T): List<T> =
    if (!p(x)) acc else go(acc + x, f(x))
  return go(emptyList(), seed)
}

class Memoizer<T,U> private constructor() {
  private val cache = java.util.concurrent.ConcurrentHashMap<T,U>()
  private fun doMemoize(f: (T)->U): (T)->U = { t -> cache.computeIfAbsent(t, f) }
  companion object { fun <T,U> memoize(f: (T)->U): (T)->U = Memoizer<T,U>().doMemoize(f) }
}