skip to content

Why does `tailrec fun factorial(n: Int): Int = if (n <= 1) 1 else n * factorial(n - 1)` fail to optimize, and how do you fix it?

level: middleimportance: must knowfreq 50%

answer

  1. Multiply happens AFTER the call -> not tail position
  2. Accumulator parameter carries the running result
  3. Compute new acc, then make the call the last expression
  4. Default param value keeps the public signature clean
  5. try/catch around the call also kills tail position

basics

~10 s

The recursive call isn't the last thing the function does — it multiplies by n afterwards. Move the running product into an extra parameter so the call becomes the final operation.

solid answer

~50 s

In `n * factorial(n - 1)` the recursive call is **not** in tail position: after it returns, the function still multiplies by `n`. Tail-call optimization requires the recursive call to be the **last operation**, with its result returned unchanged. Because a multiply happens afterward, the compiler can't reuse the frame and emits a warning, leaving ordinary recursion that can still overflow the stack. The fix is to thread the running result through an **accumulator parameter** with a default value, so the recursive call is the final expression: `tailrec fun factorial(n: Int, acc: Int = 1): Int = if (n <= 1) acc else factorial(n - 1, acc * n)`. Now the multiply (`acc * n`) is computed *before* the call, and the call itself is the last operation — the compiler rewrites it to a loop.

code

kotlin · 3 lines
kotlin
// Optimizable
tailrec fun factorial(n: Int, acc: Int = 1): Int =
    if (n <= 1) acc else factorial(n - 1, acc * n)

go deeper

for a junior

Recognizes that something happens after the call but may not name the accumulator fix.

for a middle

Identifies the multiply as breaking tail position and rewrites with an accumulator and default value.

for a senior

Knows how to hide the accumulator via a local helper and lists other non-tail traps like try/catch and Elvis.

for a principal

Can sketch the loop the compiler generates and reason about left-vs-right fold ordering implications of the rewrite.

## The problem: tail position A call is in **tail position** when it is the **last operation** the function performs and its result is returned **as-is**. The `tailrec` optimization only works for calls in tail position. In: ```kotlin tailrec fun factorial(n: Int): Int = if (n <= 1) 1 else n * factorial(n - 1) // NOT tail: multiply happens after ``` the expression `n * factorial(n - 1)` means: call `factorial(n - 1)`, **then** multiply the result by `n`. The multiplication is the actual last operation, so the function still needs its frame after the recursive call returns. The compiler cannot reuse the frame, warns that the call is not a tail call, and falls back to **ordinary recursion** — which still throws `StackOverflowError` for large `n`. ## The fix: accumulator parameter Introduce an extra parameter that carries the partial result. Compute the new accumulator **before** the call so the call itself is last: ```kotlin tailrec fun factorial(n: Int, acc: Int = 1): Int = if (n <= 1) acc else factorial(n - 1, acc * n) // tail call: nothing after it ``` Here `acc * n` is evaluated first, then passed in; the recursive `factorial(...)` is the final expression returned directly. The compiler rewrites it to: ```kotlin fun factorial(n: Int, acc: Int = 1): Int { var n1 = n var acc1 = acc while (true) { if (n1 <= 1) return acc1 val newAcc = acc1 * n1 n1 -= 1 acc1 = newAcc } } ``` ## Hiding the accumulator The default value `acc = 1` lets callers write `factorial(5)`. If you don't want to expose the parameter, wrap a private helper: ```kotlin fun factorial(n: Int): Int { tailrec fun go(n: Int, acc: Int): Int = if (n <= 1) acc else go(n - 1, acc * n) return go(n, 1) } ``` ## Other non-tail traps - Recursive call inside `try`/`catch` — never a tail call (the frame is needed for exception handling). - `return f(x) ?: default` — the `?:` runs after the call. - Logging or any work after the call. ## Takeaway The shape that optimizes is `else recurse(updatedArgs)` with **nothing wrapping the call**.

  • How can you keep the accumulator out of the public API?
    Wrap a private/local helper function that takes the accumulator and call it from the public function with the seed value.
  • Is `return foo(x) ?: bar()` a tail call to `foo`?
    No — the Elvis operator runs after foo returns, so the call is not in tail position.

saying these in an interview costs you the question

  • Thinking `n * factorial(n-1)` is a tail call
  • Adding `tailrec` without restructuring and assuming it now works
  • Not knowing the accumulator pattern
  • Believing the compiler errors rather than warns on the non-tail version

context

resolving links…