Dive C4.01.2

Tail recursion & the accumulator

Carry the answer forward instead of leaving it on the stack, and a recursion becomes a loop that runs in constant space.

The recursive count of the last dive has a hidden cost. In 1 + count t, the addition cannot run until count t returns, so every step leaves a frame waiting on the call stack. On a list of a few elements that is invisible; on a list of a million it overflows the stack. The fix is an accumulator: thread the running answer through as an argument, so the recursive call is the last thing the function does. F# turns such a tail call into a jump — a loop that reuses one frame and runs in constant stack. List.fold is this pattern named once, so the loop is written for you. Every echo below was produced by dotnet fsi.

Drain a queue Module hub

C4.01.2 · part 1

Why a plain recursion grows the stack

A recursive call is in tail position when it is the last operation — when nothing happens to its result before the function returns. The plain count is not tail recursive: the + 1 waits for the recursive call to return, so each step holds a frame. Reframe it with an accumulator and the recursive call becomes the whole right-hand side.

// NOT tail recursive: (1 + _) waits for the recursive call to return
let rec count xs =
    match xs with
    | [] -> 0
    | _ :: t -> 1 + count t      // a frame waits at every step

On a long enough list, the held frames exhaust the call stack and the program raises a StackOverflowException — a fault the CLR does not let you catch. The accumulator form below counts a million-element list with no growth in stack.

C4.01.2 · part 2

The accumulator carries the answer forward

Add a parameter that holds the result so far. At each step, fold the head into the accumulator and pass it to the recursive call — which is now in tail position. F# compiles that into a loop. The result is identical; the stack usage is not.

let rec countAcc acc xs =
    match xs with
    | [] -> acc                  // done: return the accumulator
    | _ :: t -> countAcc (acc + 1) t   // tail call: a loop
// val countAcc: acc: int -> xs: 'a list -> int
countAcc 0 [ "JOB07"; "JOB05"; "JOB02" ]   // val it : int = 3

The tail-recursive form runs over a million elements without overflowing:

countAcc 0 [ 1 .. 1000000 ]   // val it : int = 1000000

List.fold is the accumulator pattern named once. It threads an accumulator left-to-right over a list, so you rarely hand-write the loop: List.fold (fun acc _ -> acc + 1) 0 backlog — val it : int = 3.

Drain a queue with a tail-recursive loop

A consumer empties a queue the same way: claim the oldest job, add its id to an accumulator, and recurse — until the claim returns None. Step the drain below over a fixed pending set { JOB02, JOB05, JOB07 }. Each step claims the minimum id (oldest first), moves it to the claimed list, and loops; at the empty set the claim answers None and the loop returns the accumulator. The accumulator is the only state; the stack stays flat.

drain : claim the oldest → accumulate → recurse until None

the loop starts with acc = [] and a pending set of 3. Press claim ▸ to claim the oldest id.

// over the real bus: thread the queue state, accumulate claimed ids until None
let rec drain acc (now: int64) (leaseMs: int64) (st: QueueState) =
    match Jobs.claim now leaseMs st with
    | st, None            -> List.rev acc, st          // empty/paused: stop
    | st, Some (job: Job) -> drain (job.Id :: acc) now leaseMs st

Claim, accumulate, recurse — the recursive call is the last act, so the drain is a flat loop. The base case is None, the queue's way of saying empty.

C4.01.2 · part 3

The same idiom as Elixir's tail call

This is the idiom the Elixir course teaches in E4.01: a tail-recursive accumulator, the BEAM's standard way to walk a list without growing the stack. The shape is the same; the guarantee differs slightly. F# applies tail-call optimisation to direct self-recursion like this and can emit the IL .tail prefix; the BEAM guarantees last-call optimisation for every tail call.

Elixir — tail-recursive accumulator

# Elixir — acc carried forward; the call is the last act
def count(list), do: count(list, 0)
defp count([_ | t], acc), do: count(t, acc + 1)
defp count([], acc), do: acc

F# — the same accumulator (verified in FSI)

let rec countAcc acc xs =
    match xs with
    | [] -> acc
    | _ :: t -> countAcc (acc + 1) t
// val countAcc: acc: int -> xs: 'a list -> int

The efficiency note: the accumulator builds its result in reverse (newest claimed at the front of acc), so the drain ends with List.rev acc — one O(n) pass. This is the standard functional trade: prepend (O(1)) while building, reverse once (O(n)) at the end, rather than append (O(n)) at every step. The real Store.browse uses the same List.rev to present the backlog newest-first.

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The drain is exactly how a consumer empties an EchoMQ queue. Store.claim pops the oldest pending id and answers Some row, or None when the queue is empty or paused. A tail-recursive loop calls it until None, accumulating claimed ids — the base case is the queue's emptiness.

EchoMQ in F#

The claim that drives the loop, quoted verbatim from echo_fs/EchoMQ/Store.fs — note it answers None on a paused or empty queue:

/// Claim the oldest pending job: pop the minimum id (mint order) ...
/// A paused or empty queue answers `None`, leaving the pending set untouched.
let claim (now: int64) (leaseMs: int64) (st: QueueState) : QueueState * Job option =
    if st.Paused || Set.isEmpty st.Pending then
        st, None
    else
        let id = Set.minElement st.Pending
        // ... mark active, lease to now + leaseMs, return Some row

Jobs.claim delegates to Store.claim (echo_fs/EchoMQ/Jobs.fs). A standalone model of the drain loop, verified in dotnet fsi over a fixed pending list:

let claimNext (pending: string list) =
    match pending with
    | [] -> None, []
    | id :: rest -> Some id, rest

let rec drain acc pending =
    match claimNext pending with
    | None, _ -> List.rev acc
    | Some id, rest -> drain (id :: acc) rest

drain [] [ "JOB02"; "JOB05"; "JOB07" ]
// val it : string list = ["JOB02"; "JOB05"; "JOB07"]

The F# EchoMQ drains the in-memory queue with this loop today (echo_fs/EchoMQ/Store.fs, Jobs.fs — built and tested). The Valkey transport (EchoMQ.Connector) lands next; until then Connector.eval raises "EchoMQ Valkey connector: coming soon".

The loop

An accumulator turns a recursive walk into a flat loop; the base case is [] for a list, None for a claim.

The next dive

Why claim takes the minimum in O(log n): pending is a sorted Set, not a list. That is the cost model.

Where this leads

The accumulator makes a walk a loop and gives a queue drain its shape. The final dive reads the cost of these operations from the data: O(1) at the head, O(n) at the far end, and why the pending structure is a sorted Set — so the oldest id is O(log n), not O(n).

↑ C4.01 · Lists, recursion & complexity ← C4.01.1 · Cons cells & recursion C4.01.3 · Complexity on .NET →

References

Sources

Microsoft — F# documentation — recursive functions and tail calls.
FSharp.Core API reference — List.fold and the List module.
The F# Software Foundation — F#'s home on the .NET runtime.

Related in this course

Elixir — Lists, recursion & complexity (E4.01) — the tail-recursive accumulator on the BEAM.
C4.01 — Lists, recursion & complexity — the module hub.
C4.01.1 — Cons cells & recursion — the previous dive.
C4 — Algorithms & Data Structures — the chapter overview.