Tail Recursion and Optimization

Move remaining work into an accumulator

A tail-recursive call is the final operation in its branch. Kotlin's tailrec optimization can convert eligible self-recursion into iteration, avoiding growth of recursive stack frames.

Copy codetailrec fun gcd(a: Long, b: Long): Long {
    require(a >= 0 && b >= 0)
    return if (b == 0L) a else gcd(b, a % b)
}

For 48 and 18, the argument pairs become (48,18), (18,12), (12,6), (6,0), returning six. No multiplication or addition remains after a recursive call.

Marking a function tailrec does not optimize arbitrary recursion. Mutual recursion, multiple recursive branches, and post-call work require separate reasoning. Tail-call optimization also does not prevent arithmetic overflow or improve an inefficient recurrence's total work.

Exercise

Write an accumulator-based sum function with a private tail-recursive helper and public validation. Compare it to a loop.

Check: identify exactly what state moves from the stack into parameters, and explain why a branching Fibonacci implementation cannot be fixed simply by adding tailrec.

Further reading: Kotlin tail recursion