Tail-Recursive Functions

A tail-recursive function calls itself as its very last step, and Kotlin can turn that into a fast loop instead of piling up memory.

In this page:

The Stack Overflow Problem
Marking a Function tailrec
The Call Must Be in Tail Position
Tail Recursion for Large Inputs

The Stack Overflow Problem

A normal recursive function that calls itself many times, such as computing a factorial for a large number, can exhaust the call stack because each call waits for the next one to finish.

Example: The Stack Overflow Problem

markup

fun factorial(n: Long): Long {
    return if (n <= 1) 1 else n * factorial(n - 1)
}

fun main() {
    println("10! = ${factorial(10)}")
}

Marking a Function tailrec

Adding tailrec before fun asks the compiler to convert a properly-shaped recursive call into a loop, so it runs in constant stack space no matter how many times it recurses.

Example: Marking a Function tailrec

markup

tailrec fun factorial(n: Long, accumulator: Long = 1): Long {
    return if (n <= 1) accumulator else factorial(n - 1, n * accumulator)
}

fun main() {
    println("10! = ${factorial(10)}")
}

The Call Must Be in Tail Position

For the optimization to apply, the recursive call must be the last thing the function does -- its result cannot be used in any further computation like n * factorial(...), which is why an accumulator parameter is used instead.

Note: If the compiler cannot optimize a tailrec function it emits a warning -- always check for it.

Example: The Call Must Be in Tail Position

markup

tailrec fun sumUpTo(n: Int, accumulator: Int = 0): Int {
    return if (n == 0) accumulator else sumUpTo(n - 1, accumulator + n)
}

fun main() {
    println("Sum 1..100: ${sumUpTo(100)}")
}

Tail Recursion for Large Inputs

Because a tailrec function is compiled into a loop, it can safely process large inputs that would overflow the stack in an ordinary recursive implementation.

Example: Tail Recursion for Large Inputs

markup

tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

fun main() {
    println("GCD of 48 and 18: ${gcd(48, 18)}")
}

Common Mistakes

Marking a function tailrec when its recursive call is not actually the last operation performed, which the compiler will warn about and refuse to optimize.
Forgetting that a tailrec function's recursive call must not be inside a try/catch block or wrapped in additional computation after it returns.
Assuming any recursive function can be made tailrec just by adding the keyword; the call shape itself must qualify.

Chapter Summary

tailrec tells the compiler to optimize a recursive function into an iterative loop internally, avoiding stack overflow for large inputs.
The recursive call must be the very last operation in the function -- nothing may be done with its result afterward.
The compiler warns if a function marked tailrec cannot actually be optimized, so you should watch for that warning.
Tail recursion keeps recursive-style code readable while getting loop-like performance and stack safety.

🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Infix Functions Next Lesson → Nullable Types

Tail-Recursive Functions

The Stack Overflow Problem

Marking a Function tailrec

The Call Must Be in Tail Position

Tail Recursion for Large Inputs

Chapter Quiz — Complete all 7 topics to unlock

Login to run this code