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.
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.
Practice what you learned
1. Why does Elixir rely on recursion instead of traditional for-loops with mutable counters?
2. What two parts does every recursive function need?
3. What does adding an accumulator argument and making the recursive call the last operation enable?
4. What is the relationship between Enum.map and recursion?
5. What is a key difference between Enum and Stream?
Was this page helpful?
You May Also Like
The Pipe Operator
Understand how Elixir's |> pipe operator chains function calls into readable, left-to-right data transformation pipelines.
Functions and Modules in Elixir
Learn how Elixir organizes code into modules and functions, covering named functions, arity, default arguments, private functions, module attributes, and anonymous functions.
Guards and case in Elixir
Learn how Elixir's case expression and guard clauses let you branch on pattern matches with additional boolean conditions, and when to reach for cond instead.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics