tailrec
- Kotlin course
- Expert
- Lesson 4/47
- 5 min
Learn recursion safety with tailrec.
What does tailrec do?
tailrec makes a recursive function tail-recursive; the compiler turns it into a loop. This avoids stack overflow on large inputs.
Example: tailrec fun sumTo(n: Long, acc: Long = 0L): Long = if (n <= 0L) acc else sumTo(n - 1L, acc + n). Here the recursive call is the last step of the function; that is a tail call. Without tailrec, Kotlin does not convert it; large n risks stack overflow. Functions that are not tail calls produce a warning with tailrec.
Recursion with an accumulator
Many recursive functions can be rewritten as tail calls by adding an accumulator parameter. The accumulator carries the intermediate result.
Example: tailrec fun factorial(n: Long, acc: Long = 1L): Long = if (n <= 1L) acc else factorial(n - 1L, acc * n). Here acc holds the running product; each step lowers n and grows acc. Call: factorial(5L). Result is 120. This pattern scales safely to big inputs.
Practice Write tailrec sumTo
Define tailrec fun sumTo(n: Long, acc: Long = 0L): Long. If n <= 0L return acc; otherwise call sumTo(n - 1L, acc + n). In main, write println(sumTo(10L)).
Starter code
// add the keyword
fun sumTo(n: Long, acc: Long = 0L): Long =
if (n <= 0L) acc else TODO("add recursion")
fun main() {
// print the result
}Sample solution
tailrec fun sumTo(n: Long, acc: Long = 0L): Long =
if (n <= 0L) acc else sumTo(n - 1L, acc + n)
fun main() {
println(sumTo(10L))
}Expected output
55
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 When does tailrec fail?
- When the recursive call is the last step
- When Long is used
- When there is work after the recursive call Correct answer
- When an accumulator parameter is used
Explanation: tailrec only works on real tail calls.
2 Add the tailrec keyword
____ fun sumTo(n: Long, acc: Long = 0L): Long =
if (n <= 0L) acc else sumTo(n - 1L, acc + n)tailrec fun sumTo(n: Long, acc: Long = 0L): Long =
if (n <= 0L) acc else sumTo(n - 1L, acc + n)Explanation: tailrec turns tail recursion into a loop.
3 Match tailrec parts
| Term | Meaning |
|---|---|
tailrec |
Loop conversion marker |
acc |
Accumulator |
n - 1L |
Decreasing input |
if (n <= 0L) |
Base case |