Recursion in Erlang

Analogy categoryAnalogies

Why Recursion Is Central to Erlang

Erlang has no for or while loops; the language deliberately omits mutable loop counters because variables are single-assignment, so any repeated computation must be expressed as a function calling itself with new arguments on each step. This isn't a workaround — it's the idiomatic way to iterate in Erlang, and once you're comfortable thinking in terms of a base case plus a recursive case, patterns like walking a list, counting down, or building up a result all follow the same shape.

🏏

Cricket analogy: Since Erlang has no loop counter you can reassign, counting down overs is like a scorer who can't erase the scoreboard — each new over gets written as a fresh entry decrementing from the last, exactly like a recursive call passing N-1 onward instead of mutating N.

Basic Recursive Functions

Every well-formed recursive function needs at least one base case that terminates the recursion without calling itself again, and one or more recursive cases that call the function again with arguments that move measurably closer to that base case; factorial(0) -> 1; factorial(N) when N > 0 -> N * factorial(N - 1). is the textbook example, where factorial(0) is the base case and each recursive call shrinks N by one. Forgetting the base case, or writing a recursive case whose arguments never actually approach it, produces infinite recursion that eventually exhausts memory.

🏏

Cricket analogy: It's like a run-chase calculation that stops the moment the target is reached (base case) and otherwise recalculates the required run rate after every ball (recursive case) — factorial(0) is the target being reached, and each factorial(N) call is one more ball bowled.

Tail Recursion and the Accumulator Pattern

A tail call is a recursive call that is the very last thing a clause does, with no pending arithmetic or other work left to perform after it returns, and the BEAM virtual machine turns tail calls into a plain jump rather than growing the call stack — this is why sum_to(N) -> sum_to(N, 0). paired with sum_to(0, Acc) -> Acc; sum_to(N, Acc) -> sum_to(N - 1, Acc + N). can run in constant stack space no matter how large N is. The extra Acc parameter is called an accumulator, and it carries the running result forward instead of letting each call wait on the one after it to return a value that still needs combining.

🏏

Cricket analogy: It's like a scorer who keeps a single running total on the scoreboard (the accumulator) updated ball by ball, rather than writing every ball's score on a separate slip to be added up at the end — sum_to(N, Acc) carries the running total forward the same way, using no extra 'slips' of stack space.

erlang

-module(math_utils).
-export([factorial/1, sum_to/1, my_length/1]).

factorial(0) -> 1;
factorial(N) when N > 0 -> N * factorial(N - 1).

sum_to(N) -> sum_to(N, 0).

sum_to(0, Acc) -> Acc;
sum_to(N, Acc) when N > 0 -> sum_to(N - 1, Acc + N).

my_length([]) -> 0;
my_length([_ | T]) -> 1 + my_length(T).

The BEAM virtual machine performs last call optimization on every tail call, not just direct self-calls — a tail call to a completely different function, such as the final line of a server loop calling loop(NewState), also runs in constant stack space, which is the foundation of Erlang's long-running server processes.

Recursing Over Lists

Erlang lists are naturally recursive data structures — [1,2,3] is really 1 followed by the list [2,3], written in pattern-match form as [H|T] where H is the head and T is the tail — so the standard idiom for processing a list is a clause matching [] for the empty-list base case and a clause matching [H|T] that processes H and recurses on T. my_length([]) -> 0; my_length([_|T]) -> 1 + my_length(T). walks the entire list this way, and swapping the body for a tail-recursive accumulator version turns it into a constant-stack loop over arbitrarily long lists.

🏏

Cricket analogy: It's like processing a bowling figures card ball by ball: you look at the next delivery (the head) and hand the rest of the over (the tail) to be processed the same way — [H|T] pattern matching splits a list exactly like that ball-by-ball breakdown.

factorial/1 as written is not tail-recursive, because after factorial(N-1) returns, there's still a pending multiplication by N — each call adds a stack frame, so for very large N this can exhaust memory; sum_to/2, by contrast, is tail-recursive because the recursive call is the very last operation, with nothing left to do afterward.

Erlang has no loop constructs; repetition is expressed exclusively through recursive function calls.
Every recursive function needs a base case that stops the recursion and a recursive case that progresses toward it.
A tail call is a recursive call that is the last operation in a clause, with no pending work after it returns.
The BEAM optimizes tail calls into a jump instead of growing the call stack, enabling constant memory usage.
The accumulator pattern threads a running result forward as an extra parameter to enable tail recursion.
Lists are naturally recursive: [H|T] pattern matching splits a list into its head and tail for processing.
A recursive function missing a base case, or one whose arguments never approach the base case, recurses infinitely.