To implement tail-recursive algorithms with collections in Kotlin, structure your function so that:
- The recursive call is the last operation
- Any intermediate result is carried in an accumulator
- The collection is processed by index, iterator-like state, or remaining sublist
- 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
tailreconly when recursion makes the logic clearer. - Use an accumulator for partial results.
- Prefer index-based traversal over
drop,take, orsubListloops. - 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, andfindare 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.