Why tail-recursive functions are loops

Original Article ↗ Hacker News Discussion ↗

Equivalence and control flow

  • Many comments restate that tail-recursive functions are mechanically translatable to loops; normal recursion = loop + (implicit or explicit) stack.
  • Some argue the title is backwards: loops are a special case of tail calls; tail calls can also model more general control flow (e.g., state machines, mutually recursive interpreters).
  • Several people emphasize that not all tail calls are recursive and that “tail recursion” is really just a special case of “tail calls = jumps”.

Readability and maintainability

  • One camp finds iterative code easier to “scan”: fewer hidden invariants, explicit mutable state, clearer stack traces, and less risk of accidentally breaking tail-position and causing stack overflows.
  • Another camp finds recursion clearer, especially when expressed as base case + reduction of parameters; mutation-heavy loops are seen as harder to reason about.
  • Several note that the hardest bugs often stem from uncontrolled mutation, not recursion per se.

Mutation, purity, and data structures

  • Pro‑FP commenters value tail recursion for working with persistent/immutable data while still getting loop-like performance (e.g., Clojure’s loop/recur).
  • Others counter that rebinding parameters is effectively mutation in disguise; controlled mutability (e.g., Rust-style mut) can capture most benefits without FP machinery.
  • There’s debate over whether “mutation vs rebinding” is a meaningful distinction or hair-splitting.

Performance, stacks, and implementation details

  • Tail-call optimization (TCO) is described as an optimization, sometimes implicit (Scheme, some FP languages) and sometimes explicit/annotated (Scala @tailrec, Clojure recur, upcoming Rust become, Zig call modifiers).
  • Concerns: relying on implicit TCO/RVO can be fragile — tiny code changes may disable it; runtimes differ widely (JVM’s lack of general TCO, Python and V8 having none).
  • Examples show:
    • Tail-recursive ⇒ simple loop.
    • Non‑tail recursion ⇔ loop + explicit stack (e.g., DFS, recursive‑descent parsers).
    • In Erlang/Elixir, body recursion can sometimes outperform tail recursion for map.

Debugging and stack traces

  • TCO can collapse long call chains into fewer frames, making control flow harder to reconstruct than with loops.
  • Some languages allow disabling TCO in debug builds; others prefer explicit constructs (e.g., loop/recur) to avoid ambiguity and preserve predictable traces.

Higher‑order combinators vs explicit recursion

  • Several argue that in “real” FP code you rarely write raw tail recursion; you compose map, fold, filter, traversals, and other combinators instead.
  • Others push back that early exits, partial traversals, or more specialized patterns still often call for explicit tail recursion.

Use cases: trees, parsers, state machines

  • Recursive data structures (trees, lists) often feel more natural with recursion; converting to loops with explicit stacks is possible but sometimes “nasty” or less readable.
  • Non‑tail recursion always risks stack overflows unless the language grows the stack or you reify it on the heap.
  • Tail calls are highlighted as especially elegant for state machines and interpreters (e.g., direct-threaded interpreter loops, “Lambda: the Ultimate GOTO”).

Pedagogy and philosophy

  • Disagreement over whether teaching recursion without exposing call stacks is “gatekeeping” or appropriate abstraction.
  • Some see tail calls/recursion as mathematically natural; others argue that understanding the underlying stack model is crucial for large, robust systems.