Tail Recursion (tailrec)

Tail position makes recursion replaceable by a loop

A tailrec function can be optimized when its recursive call is the final operation. If the caller must multiply, append, or otherwise process the recursive result afterward, the call is not in tail position.

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

fun main() {
    check(gcd(18, 12) == 6)
    check(gcd(0, 5) == 5)
}

The Euclidean algorithm passes all remaining work as new arguments. The base case stops recursion. The example restricts inputs to avoid complications around negative remainder behavior and the minimum integer value.

Tail-call optimization prevents recursive stack growth for eligible calls; it does not make an inefficient algorithm efficient or prevent integer overflow.

Exercise

Write an iterative version and compare results for zero, equal inputs, and relatively prime inputs. Then inspect why n * factorial(n - 1) cannot be directly tail-recursive.

Check: every recursive path should move toward a base case.

Reference: Tail-recursive functions