Kotlin Tail Recursion

Standard recursion builds a chain of function calls on the stack. Deep recursion fills the stack and crashes with a StackOverflowError. Tail recursion solves this — when the recursive call is the last action in a function, Kotlin can optimize it into a loop, using constant stack space.

The Stack Problem with Regular Recursion

fun factorial(n: Long): Long {
    if (n == 0L) return 1L
    return n * factorial(n - 1)   // multiplication happens AFTER the recursive call
}
// factorial(10000)  →  StackOverflowError

// Stack fills up like this:
// factorial(5) waits for factorial(4) waits for factorial(3) waits for...
// Each call stays on the stack until the deepest one returns.

Tail-Recursive Version

tailrec fun factorial(n: Long, accumulator: Long = 1L): Long {
    if (n == 0L) return accumulator
    return factorial(n - 1, n * accumulator)  // recursive call is the LAST action
}

fun main() {
    println(factorial(5))          // 120
    println(factorial(20))         // 2432902008176640000
    println(factorial(100_000))    // very large number — no stack overflow!
}

Tail Call Diagram

Regular recursion — stack grows:
  factorial(4)
  └── 4 * factorial(3)
            └── 3 * factorial(2)
                      └── 2 * factorial(1)
                                └── 1 * factorial(0)
  Stack depth = N

Tail recursion — Kotlin converts to a loop:
  factorial(4, 1)
  → factorial(3, 4)
  → factorial(2, 12)
  → factorial(1, 24)
  → factorial(0, 24)
  → return 24
  Stack depth = 1 (constant)

Rules for tailrec

For tailrec to work:
  ✓ The recursive call must be the LAST operation
  ✓ The function must be a direct call to itself
  ✗ Cannot be used when result is: n * factorial(n-1)
    (multiplication happens AFTER the call — not tail-recursive)
  ✗ Cannot be used in try-catch blocks around the recursive call

Tail-Recursive Fibonacci

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

fun main() {
    for (i in 0..10) {
        print("${fibonacci(i)} ")
    }
    // 0 1 1 2 3 5 8 13 21 34 55

    println(fibonacci(50))   // 12586269025 — no overflow, no crash
}

Tail-Recursive Sum

tailrec fun sumUpTo(n: Long, acc: Long = 0L): Long {
    if (n == 0L) return acc
    return sumUpTo(n - 1, acc + n)
}

fun main() {
    println(sumUpTo(100))         // 5050
    println(sumUpTo(1_000_000))   // 500000500000
}

Compiler Verification

The tailrec modifier causes a compile-time warning if the recursion is not actually tail-recursive. This is a safety net — it confirms the optimization will be applied:

// This will NOT compile with tailrec (multiplication after recursive call):
tailrec fun wrongFactorial(n: Long): Long {
    if (n == 0L) return 1L
    return n * wrongFactorial(n - 1)   // WARNING: not tail recursive
}

Practical Example: Deep List Search

tailrec fun findInList(list: List, target: Int, index: Int = 0): Int {
    if (index >= list.size) return -1
    if (list[index] == target) return index
    return findInList(list, target, index + 1)
}

fun main() {
    val bigList = (1..100_000).toList()
    println(findInList(bigList, 75000))   // 74999 (index)
    println(findInList(bigList, 200000))  // -1 (not found)
}

This searches a list of 100,000 items recursively with zero risk of a stack overflow because the tailrec optimizer converts the recursion into a loop behind the scenes.