blog :: Post "tail-calls"

Tail Calls

2026-09-13 · 8 min

A tail call is a call whose result is returned directly, with nothing left to do afterwards. The frame that made it is dead at the moment of the call, so it can be reused instead of stacked. Whether that actually happens depends on the language, and in several of them it depends on the compiler flags.

§ 01

Tail position

Not a tail call. The addition happens after the recursive call returns, so every frame has to stay.

let rec length = function
  | [] -> 0
  | _ :: xs -> 1 + length xs

A tail call. The result of the recursive call is the result of the function.

let rec length acc = function
  | [] -> acc
  | _ :: xs -> length (acc + 1) xs

Positions that look close but are not tail position.

f x + 1              (* pending addition *)
g (f x)              (* pending call to g *)
if f x then a else b (* result is used as a condition *)
try f x with _ -> 0  (* handler must stay installed *)
(f x, g y)           (* pending construction *)

§ 02

Guaranteed

Scheme requires proper tail calls in the standard. Iteration is expressed as recursion and there is no separate loop construct needed.

(define (loop n acc)
  (if (= n 0)
      acc
      (loop (- n 1) (+ acc n))))
 
(loop 10000000 0)   ; constant stack

OCaml guarantees tail calls in both the native and bytecode compilers. Mutual recursion is included.

let rec even n = if n = 0 then true  else odd  (n - 1)
and     odd  n = if n = 0 then false else even (n - 1)
 
let () = print_endline (string_of_bool (even 10_000_000))

Annotate the call and the compiler checks you. Warning 51 fires if it is not in tail position, which is how you stop a refactor from quietly reintroducing stack growth.

let rec sum acc = function
  | [] -> acc
  | x :: xs -> (sum [@tailcall]) (acc + x) xs

The caveat in OCaml: a call passing more arguments than fit in registers is not turned into a jump. Rare, but it is a real cliff, and the annotation is what surfaces it.

$ ocamlopt -w +51 main.ml

§ 03

Only if you ask

C and C++ have no guarantee. GCC and Clang perform sibling call optimization at -O2 and not at -O0, so the same source overflows or does not depending on the build.

$ g++ -O0 loop.cpp && ./a.out   # segfault
$ g++ -O2 loop.cpp && ./a.out   # fine

Clang's musttail turns it into a contract. If the call cannot be compiled as a tail call, the build fails rather than the program.

int run(State* s);
 
int step(State* s) {
  if (s->done) return s->result;
  advance(s);
  [[clang::musttail]] return run(s);
}

musttail requires the signatures to match exactly, including return type and parameter types. That restriction is why it works for interpreter dispatch and parser state machines and not much else.

error: cannot perform a tail call to function 'run'
because its signature is incompatible with the caller

Rust has no guarantee. become is reserved for this and not implemented, so today you write the loop.

fn sum(mut n: u64, mut acc: u64) -> u64 {
    while n > 0 {
        acc += n;
        n -= 1;
    }
    acc
}

§ 04

Not available

The JVM has no tail call instruction. Scala's @tailrec compiles direct self-recursion into a loop, and fails the build when it cannot.

import scala.annotation.tailrec
 
@tailrec
def sum(n: Int, acc: Int): Int =
  if (n == 0) acc else sum(n - 1, acc + n)

It only covers a function calling itself. Mutual recursion is rejected.

error: could not optimize @tailrec annotated method even:
it contains a recursive call not in tail position

Clojure makes it explicit rather than implicit. recur is checked at compile time and rebinds the loop, so there is no question about whether you got it.

(loop [n 10000000 acc 0]
  (if (zero? n)
    acc
    (recur (dec n) (+ acc n))))

JavaScript specified proper tail calls in ES2015. Only JavaScriptCore shipped them, so in practice they are not available.

'use strict';
const loop = (n, acc) => n === 0 ? acc : loop(n - 1, acc + n);
 
loop(1e7, 0);  // RangeError on V8 and SpiderMonkey

Python declines deliberately. Raising the limit moves the failure rather than removing it, since the C stack is the real bound.

import sys
sys.setrecursionlimit(100000)   # still segfaults eventually

§ 05

Haskell asks a different question

GHC compiles tail calls as jumps, so tail position is not the issue. Laziness is. A tail-recursive function that builds an unevaluated accumulator moves the problem from the stack to the heap, and the overflow happens later, when the thunk chain is forced.

Tail recursive, and it still overflows. acc is a chain of ten million pending additions by the time the list ends.

sumL :: [Int] -> Int
sumL = go 0
  where go acc []     = acc
        go acc (x:xs) = go (acc + x) xs
 
main = print (sumL [1..10000000])

Force the accumulator at each step and it runs in constant space. The bang is the whole fix.

{-# LANGUAGE BangPatterns #-}
 
sumL :: [Int] -> Int
sumL = go 0
  where go !acc []     = acc
        go !acc (x:xs) = go (acc + x) xs

Which is what foldl' already does, and why foldl is the wrong default.

import Data.List (foldl')
 
total = foldl' (+) 0 [1..10000000]

The reverse case: foldr is not tail recursive and works anyway, because a lazy combining function never forces the rest.

anyTrue :: [Bool] -> Bool
anyTrue = foldr (||) False
 
anyTrue (True : repeat False)   -- returns immediately

§ 06

Recursion that builds something

The common non-tail case is not arithmetic, it is a function returning a constructor: the recursive call happens inside a cons cell. Rewriting by hand means an accumulator and a reversal at the end.

Not tail recursive. The stdlib List.map is this, which is why it overflows on long lists.

let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

The manual fix: accumulate backwards, then reverse.

let map f xs =
  let rec go acc = function
    | [] -> List.rev acc
    | x :: xs -> go (f x :: acc) xs
  in go [] xs

Or let the compiler do it. tail_mod_cons, from OCaml 4.14, rewrites constructor-returning recursion into a tail-recursive version that fills the cell in afterwards. Same source, constant stack, no reversal.

let[@tail_mod_cons] rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

§ 07

When the language will not do it

A trampoline. The function returns a description of the next step instead of calling it, and a loop runs the steps. Constant stack in any language.

type 'a step = Done of 'a | More of (unit -> 'a step)
 
let rec run = function
  | Done x -> x
  | More k -> run (k ())
 
let rec even n = if n = 0 then Done true  else More (fun () -> odd  (n - 1))
and     odd  n = if n = 0 then Done false else More (fun () -> even (n - 1))
 
let () = ignore (run (even 10_000_000))

An explicit stack. Turn the frames the runtime would have kept into a data structure you control, which also lets you bound it.

let sum_tree t =
  let rec go acc = function
    | [] -> acc
    | Leaf n :: rest -> go (acc + n) rest
    | Node (l, r) :: rest -> go acc (l :: r :: rest)
  in go 0 [t]

§ 08

Checking

Look at what was emitted. A tail call is a jmp; a stacked call is a call followed by more work.

$ objdump -d ./a.out | sed -n "/<loop>:/,/ret/p"
  401136:  48 01 f7   add    %rsi,%rdi
  401139:  e9 c2 ff.. jmp    401100 <loop>

Or measure it, which needs no tooling and catches the cases the annotations miss.

$ ulimit -s 1024
$ ./prog
constant stack: finishes. growing stack: killed.

The checks each language gives you, in order of how much they promise.

clang    [[clang::musttail]]     build fails if not a tail call
Scala    @tailrec                build fails if not self-tail-recursive
Clojure  recur                   build fails if not in tail position
OCaml    [@tailcall] with -w +51 warns if not a tail call
GHC      -fprof-late, +RTS -s    measure, since tail position is not the issue

§ 09

Summary

Where each language stands.

Scheme      guaranteed by the standard
OCaml       guaranteed, including mutual recursion
Erlang      guaranteed; the process loop depends on it
Lua         guaranteed for calls written as return f(x)
Haskell     compiled as jumps; strictness is the real concern
C, C++      at -O2 in practice; musttail to require it
Rust        no; become reserved, not implemented
Scala       self-recursion only, via @tailrec
Clojure     explicit, via recur and trampoline
Java, Kotlin no on the JVM; Kotlin has tailrec for self-recursion
JavaScript  specified, shipped only in JavaScriptCore
Python      declined by design

The practical position: on OCaml, Scheme, and Erlang, write the recursion and annotate it so a refactor cannot break it silently. On the JVM and in Rust, write the loop. In C and C++, use musttail when the tail call is load-bearing rather than trusting the optimizer. In Haskell, stop thinking about tail position and check strictness instead.