Recursion and Enum

Analogy categoryAnalogies

Why Elixir Uses Recursion

Elixir data structures are immutable, so there's no variable to mutate in place across iterations the way an imperative for-loop increments a counter. Recursion -- a function calling itself with a smaller version of the problem -- is the fundamental looping mechanism instead: each call produces a new value built from the previous one, rather than rewriting an existing value in memory.

🏏

Cricket analogy: Since Elixir values can't be mutated in place, you can't 'erase and rewrite' a running total like a scorer updating one chalk slate -- each new total is a fresh value built from the last, similar to a tally sheet appending a new cumulative figure after every delivery.

Writing a Recursive Function

A recursive function needs a base case that stops the recursion and returns a concrete result, and a recursive case that makes progress toward that base case. Summing a list is the canonical example: sum([]) matches the base case and returns 0, while sum([head | tail]) matches the recursive case, returning head + sum(tail) -- pattern matching on [head | tail] is the idiomatic way to destructure and recurse through a list element by element.

🏏

Cricket analogy: sum_runs([]) returning 0 is the base case declaring 'an innings with no more deliveries left contributes zero further runs,' while sum_runs([ball | rest]) computing ball + sum_runs(rest) tallies the current delivery's runs plus everything still to come, the way a scorer's running total accumulates ball by ball.

elixir

defmodule ListMath do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)

  def sum_tail(list), do: sum_tail(list, 0)
  defp sum_tail([], acc), do: acc
  defp sum_tail([head | tail], acc), do: sum_tail(tail, acc + head)
end

ListMath.sum([1, 2, 3, 4])       # 10
ListMath.sum_tail([1, 2, 3, 4])  # 10 (tail-recursive, constant stack)

Enum.reduce([1, 2, 3, 4], 0, &(&1 + &2))  # 10
Enum.map([1, 2, 3], &(&1 * &1))           # [1, 4, 9]
Enum.filter(1..10, &(rem(&1, 3) == 0))    # [3, 6, 9]

Tail Call Optimization

A tail-recursive function passes an accumulator argument and makes the recursive call the very last operation in its body, as in sum_tail([head | tail], acc), do: sum_tail(tail, acc + head). Because that call is in 'tail position,' the BEAM can reuse the current stack frame instead of pushing a new one, executing the recursion in constant stack space, unlike the non-tail sum([head | tail]), do: head + sum(tail), where each call must wait for the one below it to return before it can compute head + ....

🏏

Cricket analogy: A tail-recursive sum_runs(list, acc) is like a scorer updating one running total after every ball, never keeping a stack of partial scorecards, while the non-tail version keeps each delivery's calculation open, nested inside the one before, resolving only once the last ball is bowled.

Non-tail recursion on very long lists can accumulate a large call stack because each pending call (like head + sum(tail)) must stay alive waiting for the deeper call to return. Prefer a tail-recursive accumulator pattern, or an Enum/Stream function that already handles this internally, when processing lists that could be arbitrarily long.

The Enum Module

The Enum module wraps common recursive patterns -- Enum.map/2, Enum.filter/2, Enum.reduce/3 -- into ready-made, well-tested functions, and is implemented internally using recursion just like the hand-written examples above. Stream, by contrast, builds a lazy pipeline that computes values only as they're consumed, avoiding the intermediate lists that Enum eagerly builds at each step -- useful when chaining several transformations over a large or infinite collection.

🏏

Cricket analogy: Enum.map is like handing a stat-conversion task to Hawk-Eye's analytics team instead of manually recalculating every delivery's trajectory yourself -- the system internally still processes each ball one by one, just packaged behind a clean request.

Stream functions like Stream.map/2 and Stream.filter/2 return a lazy, composable stream rather than a realized list -- nothing actually runs until the stream is consumed by something like Enum.to_list/1, Enum.take/2, or another Enum function. This makes Stream ideal for chaining several transformations over large files or infinite ranges without building intermediate lists at every step.

Elixir data structures are immutable, so recursion (not mutation) is the fundamental looping mechanism.
A recursive function needs a base case that stops recursion and a recursive case that makes progress toward it.
Pattern matching on [head | tail] is the idiomatic way to recurse over lists element by element.
Tail-recursive functions carry an accumulator argument and let the BEAM optimize away growing stack frames.
Non-tail recursion can build a large call stack on very long lists since each pending call waits on the next.
The Enum module provides ready-made functions like map, filter, and reduce built internally on recursion.
Stream offers lazy, on-demand evaluation as an alternative to Enum's eager evaluation for large or infinite data.