skip to content

Show how to factor a recursive algorithm into a local function. Why is a local function often preferred over exposing the recursive helper as a separate public/member function?

level: middleimportance: should knowfreq 45%

answer

  1. public fn = clean signature, nested go() = bookkeeping
  2. capture list/target instead of re-passing
  3. helper stays private, no API noise
  4. tailrec on local fn -> loop, no stack overflow
  5. tailrec needs call in tail position

basics

~20 s

Put the recursive part in a function declared inside the public one. It keeps the recursion private and lets it reuse the outer parameters, so the public function's signature stays clean and the helper can't be misused from outside.

solid answer

~40 s

Recursive algorithms often need an extra accumulator or index parameter that callers shouldn't see. A local function lets you keep the clean public signature while the recursion carries the extra state internally, and it can close over fixed inputs (like the target list or a comparator) so they don't have to be passed on every recursive call. Encapsulation is the main win: the helper isn't part of the public/member API, so nothing else can call it with wrong arguments. You can still mark a local function `tailrec` to get the compiler's tail-call optimization (loop rewrite, avoiding stack growth) when the recursive call is in tail position. The alternative — a separate `private` member — works but leaks an extra method and forces you to thread shared inputs through parameters.

code

kotlin · 8 lines
kotlin
fun fib(n: Int): Long {
    tailrec fun go(i: Int, a: Long, b: Long): Long =
        if (i == 0) a else go(i - 1, b, a + b) // tail position
    require(n >= 0)
    return go(n, 0, 1)
}

fun main() = println(fib(50)) // 12586269025

go deeper

for a junior

Can write a simple recursive local function with a base case and recursive case.

for a middle

Explains the clean-signature/encapsulation motivation and uses an accumulator + captured inputs.

for a senior

Knows tailrec semantics, tail-position requirement, and StackOverflow risk for non-tail recursion.

for a principal

Judges when recursion should be promoted/replaced (iteration, sequences) for clarity and stack safety at scale.

## The pattern Many recursive algorithms need bookkeeping parameters (an index, an accumulator, depth) that the public caller shouldn't have to supply. A local function lets the **public function** expose a clean signature while a **nested helper** carries the bookkeeping and reuses the outer inputs via closure. ```kotlin fun sumList(numbers: List<Int>): Int { fun go(index: Int, acc: Int): Int = if (index == numbers.size) acc // base case else go(index + 1, acc + numbers[index]) // recursive step; `numbers` captured return go(0, 0) } ``` Here `numbers` is captured, so it isn't repeated in every recursive call, and `go` is invisible outside `sumList`. ## Why prefer it over a separate public/member helper - **Encapsulation:** the helper isn't part of any public or class-level API, so callers can't invoke it with invalid `index`/`acc` values that break the invariant. - **No API noise:** you don't add a `private fun goImpl(...)` member that exists only to serve one function. - **State sharing:** captured `val`s (the list, a comparator, a target) don't need to be threaded through every call. ## tailrec on a local function A local function can be marked **`tailrec`**. When the recursive call is the **last operation** (tail position), the compiler rewrites the recursion into a loop, so deep inputs don't blow the call stack with a `StackOverflowError`. ```kotlin fun factorial(n: Int): Long { tailrec fun go(i: Int, acc: Long): Long = if (i <= 1) acc else go(i - 1, acc * i) // call is in tail position return go(n, 1L) } ``` If the recursive call were *not* in tail position (e.g. `i * go(i - 1)`), `tailrec` would emit a warning and keep ordinary recursion. ## Caveats - Deep non-tail recursion in a local function still risks `StackOverflowError` — `tailrec` only helps tail-position calls. - A local function name must be declared before it's used, but it may call itself (its own name is in scope within its body). ## When NOT to use it If the recursive helper is genuinely reusable by several functions, promote it to a `private` member or top-level function instead.

  • What does `tailrec` require to actually optimize the recursion?
    The recursive call must be the last operation in the function (tail position). Otherwise the compiler warns and keeps normal recursion.
  • Can a local function call itself recursively?
    Yes — its own name is in scope within its body, so it can recurse like any named function.

saying these in an interview costs you the question

  • Thinking any recursion automatically becomes a loop without `tailrec` and a tail-position call
  • Putting the recursive call inside an expression (e.g. n * go(...)) and still expecting tailrec to optimize it
  • Exposing the bookkeeping helper as a public method that callers can misuse
  • Re-passing captured constants on every recursive call unnecessarily
  • Claiming local functions can't be recursive

context

resolving links…