To implement tail-recursive algorithms with collections in Kotlin, structure your function so that:

1. The recursive call is the last operation
2. Any intermediate result is carried in an accumulator
3. The collection is processed by index, iterator-like state, or remaining sublist
4. You mark the function with tailrec

Basic pattern

tailrec fun process(
    items: List<Int>,
    index: Int = 0,
    acc: Int = 0
): Int {
    return if (index == items.size) {
        acc
    } else {
        process(items, index + 1, acc + items[index])
    }
}

The recursive call to process(...) is the final operation, so Kotlin can optimize it into a loop.

Example: sum a list

tailrec fun sum(
    numbers: List<Int>,
    index: Int = 0,
    acc: Int = 0
): Int {
    return if (index == numbers.size) {
        acc
    } else {
        sum(numbers, index + 1, acc + numbers[index])
    }
}

fun main() {
    println(sum(listOf(1, 2, 3, 4))) // 10
}

Here, acc stores the running total.

Example: find an element

tailrec fun <T> containsItem(
    items: List<T>,
    target: T,
    index: Int = 0
): Boolean {
    return when {
        index == items.size -> false
        items[index] == target -> true
        else -> containsItem(items, target, index + 1)
    }
}

fun main() {
    val names = listOf("Ada", "Grace", "Linus")

    println(containsItem(names, "Grace")) // true
    println(containsItem(names, "Kotlin")) // false
}

This is tail-recursive because each branch either returns a value directly or calls the function as the last action.

Example: map a collection

For transformations, use an accumulator collection.

tailrec fun <T, R> mapTailrec(
    items: List<T>,
    transform: (T) -> R,
    index: Int = 0,
    acc: MutableList<R> = mutableListOf()
): List<R> {
    return if (index == items.size) {
        acc
    } else {
        acc.add(transform(items[index]))
        mapTailrec(items, transform, index + 1, acc)
    }
}

fun main() {
    val result = mapTailrec(listOf(1, 2, 3)) { it * 2 }
    println(result) // [2, 4, 6]
}

This works, but note that it uses a mutable accumulator internally.

If you want a public immutable-looking API, wrap it:

fun <T, R> List<T>.mapTailrec(transform: (T) -> R): List<R> {
    tailrec fun loop(
        index: Int,
        acc: MutableList<R>
    ): List<R> {
        return if (index == size) {
            acc
        } else {
            acc.add(transform(this[index]))
            loop(index + 1, acc)
        }
    }

    return loop(0, ArrayList(size))
}

Usage:

val doubled = listOf(1, 2, 3).mapTailrec { it * 2 }
println(doubled) // [2, 4, 6]

Example: filter a collection

fun <T> List<T>.filterTailrec(predicate: (T) -> Boolean): List<T> {
    tailrec fun loop(
        index: Int,
        acc: MutableList<T>
    ): List<T> {
        if (index == size) {
            return acc
        }

        val item = this[index]

        if (predicate(item)) {
            acc.add(item)
        }

        return loop(index + 1, acc)
    }

    return loop(0, mutableListOf())
}

Usage:

val evens = listOf(1, 2, 3, 4, 5, 6).filterTailrec { it % 2 == 0 }
println(evens) // [2, 4, 6]

Example: fold with tail recursion

A tail-recursive fold is a good general building block:

tailrec fun <T, R> foldTailrec(
    items: List<T>,
    index: Int = 0,
    acc: R,
    operation: (R, T) -> R
): R {
    return if (index == items.size) {
        acc
    } else {
        foldTailrec(
            items = items,
            index = index + 1,
            acc = operation(acc, items[index]),
            operation = operation
        )
    }
}

Usage:

val numbers = listOf(1, 2, 3, 4)

val sum = foldTailrec(numbers, acc = 0) { acc, n -> acc + n }
val product = foldTailrec(numbers, acc = 1) { acc, n -> acc * n }

println(sum)     // 10
println(product) // 24

Avoid this: non-tail recursion

This is not tail-recursive:

fun sumBad(numbers: List<Int>): Int {
    return if (numbers.isEmpty()) {
        0
    } else {
        numbers.first() + sumBad(numbers.drop(1))
    }
}

The recursive call is not the last operation because Kotlin still has to add numbers.first() after sumBad(...) returns.

This is also inefficient because drop(1) creates new lists repeatedly.

Prefer index-based traversal for lists

For lists, prefer this:

tailrec fun sumGood(
    numbers: List<Int>,
    index: Int = 0,
    acc: Int = 0
): Int {
    return if (index == numbers.size) {
        acc
    } else {
        sumGood(numbers, index + 1, acc + numbers[index])
    }
}

Instead of this:

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

Even though the second version is tail-recursive, drop(1) allocates a new list each time, which can make the algorithm much slower.

Important limitation

Kotlin’s tailrec optimization works only for direct self-recursion.

This can be optimized:

tailrec fun countDown(n: Int) {
    if (n > 0) countDown(n - 1)
}

But this cannot:

fun even(n: Int): Boolean {
    return n == 0 || odd(n - 1)
}

fun odd(n: Int): Boolean {
    return n != 0 && even(n - 1)
}

Mutual recursion is not optimized by tailrec.

Practical advice

For collection algorithms in Kotlin:

• Use tailrec only when recursion makes the logic clearer.
• Use an accumulator for partial results.
• Prefer index-based traversal over drop, take, or subList loops.
• For transformations, use a mutable accumulator internally and return it as List<T>.
• Remember that Kotlin’s standard library functions like map, filter, fold, any, and find are usually the best choice in production code.

In most real Kotlin code, this:

val result = numbers.fold(0) { acc, n -> acc + n }

is preferable to writing your own recursive fold unless you are learning, implementing custom traversal logic, or working with recursive data structures.