Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 48 ยท Core Language

Recursion and Tail Calls

Learn recursion in Elixir: base and recursive cases, accumulators, body vs tail recursion, tail-call optimization on the BEAM and when to use Enum instead.

Elixir has no for or while loop that changes a variable. Data is immutable, so there is nothing to increment. Instead, a function that has more work to do simply calls itself with a smaller or updated piece of data. That is recursion, and it is how Elixir's own Enum functions are built.

Recursion sounds risky if you know it from languages where deep recursion overflows the stack. On the BEAM (the Erlang virtual machine) the story is better: a call in tail position reuses the current stack frame, so a tail-recursive function can run a billion times in constant memory. This lesson shows how to write recursive functions with multiple clauses, what an accumulator is, and the difference between body and tail recursion.

Elixir does not run on this site. Elixir code is read-only; the runnable blocks are JavaScript stand-ins. Careful: JavaScript engines do not guarantee tail-call optimization, so a deep JavaScript stand-in can overflow, while real Elixir would not.

The two parts of every recursion

A recursive function needs:

  1. A base case that stops the recursion and returns a result directly.
  2. A recursive case that does a bit of work and calls the function again on something smaller, so it moves toward the base case.

Summing a list shows both. The empty list is the base case; a non-empty list is split into head and tail with [head | tail]:

ELIXIR
defmodule MyList do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

MyList.sum([4, 7, 9])   # 20

Evaluating sum([4, 7, 9]) expands like this:

TEXT
sum([4, 7, 9])
4 + sum([7, 9])
4 + (7 + sum([9]))
4 + (7 + (9 + sum([])))
4 + (7 + (9 + 0))
20

Each clause handles one shape of input, which is why pattern matching and recursion go together so well. If you forget the base case, the function eventually receives [] and raises a FunctionClauseError, a loud and easy-to-find bug (instead of an endless loop).

Recursion in three steps

Base case The simplest input has a direct answer.
Shrink Split off the head and keep the tail.
Call again Combine the head with the result for the tail.

Every call must move closer to the base case.

1 / 2

A JavaScript stand-in

The same function in JavaScript, using the same two cases:

JS Sum a list recursively

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Body recursion and its cost

The sum/1 above is body-recursive: after the inner call returns, there is still work to do (head + ...). The runtime must remember each pending addition, so the stack grows with the length of the list. On the BEAM this is not an immediate disaster, because the stack lives on the process heap and grows as needed (until memory runs out), but it uses memory proportional to the input.

Body recursion is still fine, and often the clearest choice, when it builds a new list of the same size, as map does:

ELIXIR
def double([]), do: []
def double([head | tail]), do: [head * 2 | double(tail)]

Modern BEAM versions handle this pattern well, so do not avoid it out of fear. Measure before you rewrite.

Tail recursion with an accumulator

A call is in tail position when its result is returned unchanged: nothing happens after it comes back. To get there, carry the running result in an extra parameter, the accumulator:

ELIXIR
defmodule MyList do
  def sum(list), do: sum(list, 0)

  defp sum([], acc), do: acc
  defp sum([head | tail], acc), do: sum(tail, acc + head)
end

Now the last thing sum/2 does is call itself. There is nothing left to add after the call, so the runtime performs tail-call optimization (TCO): it jumps back to the start of the function, reusing the stack frame. The call sequence looks like a loop:

TEXT
sum([4, 7, 9], 0)
sum([7, 9], 4)
sum([9], 11)
sum([], 20)
20

The public sum/1 hides the accumulator. The private sum/2 does the work. This "public wrapper plus private helper with an accumulator" shape is the standard idiom.

flowchart LR
    A["sum([4,7,9], 0)"] --> B["sum([7,9], 4)"]
    B --> C["sum([9], 11)"]
    C --> D["sum([], 20)"]
    D --> E["returns 20"]

Tail recursion passes the running total forward, so no work is waiting on the way back.

The tail call must be the last operation. These are not tail calls:

ELIXIR
def a(n), do: 1 + a(n - 1)           # addition happens after
def b(n), do: [n | b(n - 1)]         # list construction happens after
def c(n), do: {:ok, c(n - 1)}        # tuple wrapping happens after

Calls inside case, if and cond branches are tail calls if they are the final expression in the branch.

JS Accumulator style in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Reversal, the accumulator's best friend

With an accumulator, lists get built backwards, because prepending ([x | acc]) is cheap and appending is not (see tuples and lists). That is why many tail-recursive functions finish with Enum.reverse/1:

ELIXIR
defmodule Numbers do
  def evens(list), do: evens(list, [])

  defp evens([], acc), do: Enum.reverse(acc)
  defp evens([h | t], acc) when rem(h, 2) == 0, do: evens(t, [h | acc])
  defp evens([_ | t], acc), do: evens(t, acc)
end

Numbers.evens([1, 2, 3, 4, 5, 6])   # [2, 4, 6]

Notice the three clauses: the base case, a clause with a guard that keeps the element, and a clause that skips it. Never write acc ++ [h] in a loop; each ++ copies the whole left list, turning a linear algorithm into a quadratic one.

JS Filtering with an accumulator, then reversing

Press Run (or Ctrl + Enter) to see the console output here.

No output.

More shapes of recursion

Recursion is not only for lists. Counting, numbers and trees follow the same plan.

ELIXIR
defmodule Math2 do
  def factorial(0), do: 1
  def factorial(n) when n > 0, do: n * factorial(n - 1)

  def countdown(0), do: [:liftoff]
  def countdown(n) when n > 0, do: [n | countdown(n - 1)]

  def fib(n), do: fib(n, 0, 1)
  defp fib(0, a, _b), do: a
  defp fib(n, a, b), do: fib(n - 1, b, a + b)
end

Math2.factorial(5)   # 120
Math2.fib(10)        # 55

factorial/1 is body-recursive and clear. fib/3 is tail-recursive with two accumulators and runs in linear time; the naive fib(n - 1) + fib(n - 2) is exponential.

Elixir integers have arbitrary size, so factorial(50) simply gives a very large number with no overflow.

Do you need to write recursion yourself?

Usually not. Enum.map/2, Enum.filter/2, Enum.reduce/3 and friends already encode the common patterns, and they are well tested and fast. Write explicit recursion when:

  • you walk a custom structure, such as a tree or nested maps,
  • the loop has an unusual stopping rule or several accumulators,
  • you are writing a long-running process loop (you will meet this in the concurrency chapter, where a process calls itself in tail position to keep its state forever),
  • or you want to understand what Enum does under the hood.

Otherwise reach for Enum first. Enum.reduce/3 is, in effect, a tail-recursive loop with an accumulator where you supply only the step.

ELIXIR
Enum.reduce([4, 7, 9], 0, fn n, acc -> acc + n end)   # 20

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two required parts of a recursive function?

    The base case stops the recursion; the recursive case calls the function again on smaller input so the base case is eventually reached.
  2. 2. Which function is tail-recursive?

    Only the accumulator version makes the recursive call the very last operation. The others add, build a list or wrap a tuple after the call returns.
  3. 3. Why do accumulator-based list functions often end with Enum.reverse/1?

    Adding to the front of a linked list is O(1), while appending copies the list. Building in reverse and reversing once keeps the whole function linear.
  4. 4. What does tail-call optimization give you on the BEAM?

    When the recursive call is the last operation, no work is waiting for it, so the runtime can jump instead of pushing a new frame.
  5. 5. When is it best to use Enum.reduce/3 instead of writing the recursion yourself?

    Enum functions already implement the standard patterns. Hand-written recursion is for custom structures and unusual loops.

Summary

  • Elixir repeats work by recursion: a base case plus a recursive case on smaller data.
  • Pattern matching in multiple clauses makes each case short and explicit.
  • Body recursion does work after the call returns and uses stack proportional to the input; it is fine for building same-size lists.
  • Tail recursion makes the call last, usually with an accumulator, and the BEAM then reuses the stack frame (tail-call optimization).
  • Build lists by prepending, then reverse once; avoid ++ in loops.
  • Prefer Enum functions unless you need custom traversal.
  • JavaScript stand-ins here are for understanding only; JavaScript does not guarantee tail-call optimization.

Next, put these ideas to work on whole collections in The Enum Module.