Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 36 ยท Functions and Pattern Matching

Recursion and Tail Calls

Replace loops with recursion in Erlang: base cases, list recursion, accumulators, tail-call optimization, and why tail recursion keeps long-running servers alive.

Erlang has no for or while. To repeat work, a function calls itself. This feels odd at first but follows a simple recipe: handle the base case (the end), and for everything else do one step and recurse on the rest. Pattern matching makes the recipe short.

Your first recursive function

ERLANG
-module(recur).
-export([factorial/1, sum/1, len/1]).

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

factorial(0) is the base case, and every other call reduces N by one. Evaluating factorial(4) expands to 4 * (3 * (2 * (1 * 1))).

For lists the base case is the empty list, and the recursive case uses [H | T]:

ERLANG
sum([]) -> 0;
sum([H | T]) -> H + sum(T).

len([]) -> 0;
len([_ | T]) -> 1 + len(T).
ERLANG
1> recur:sum([1, 2, 3, 4]).
10
2> recur:len([a, b, c]).
3

The recipe is always: what is the answer for []? And how do I combine the head with the answer for the tail?

The cost of body recursion

In sum/1 above, after the recursive call returns, there is still work to do (H + ...). The runtime must remember each pending addition on the call stack, so a list of a million elements creates a million waiting frames. Erlang's stack grows on the heap so it will not overflow quickly, but memory is used proportional to the list length, and for endless loops it grows without end.

Tail recursion and accumulators

A call is a tail call when it is the very last thing the function does. The runtime reuses the current frame for a tail call, so it runs in constant space, exactly like a loop. To make sum tail-recursive we pass the running total as an extra argument, the accumulator:

ERLANG
sum(List) -> sum(List, 0).

sum([], Acc) -> Acc;
sum([H | T], Acc) -> sum(T, Acc + H).

Now the recursive call sum(T, Acc + H) is the final action. The base case returns the accumulated answer. Typically the public function has a short name and calls a private helper with the same name and a bigger arity, so callers never see the accumulator.

Factorial the same way:

ERLANG
factorial(N) -> factorial(N, 1).

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

Building lists with accumulators

Accumulating a list puts new elements at the front, so the result comes out reversed; fix this with lists:reverse/1 at the end:

ERLANG
double(List) -> double(List, []).

double([], Acc) -> lists:reverse(Acc);
double([H | T], Acc) -> double(T, [H * 2 | Acc]).

Prepending with [X | Acc] is constant time, while Acc ++ [X] copies the whole accumulator each time and turns a linear algorithm into a quadratic one. Note that for simple building, a body-recursive double([H|T]) -> [H*2 | double(T)] is also fine on modern Erlang, which optimizes it well; measure before assuming one is slower.

Infinite loops are fine

A long-running process, such as a server, is just a tail-recursive function that never returns:

ERLANG
loop(State) ->
    receive
        {add, N} -> loop(State + N);
        {get, From} -> From ! State, loop(State);
        stop -> ok
    end.

Each branch ends with a tail call to loop/1 or returns. This runs in constant memory forever. The only mistake to avoid is wrapping the recursive call in something that adds work after it, for example loop(State + N) + 1 or inside a try ... catch expression that must be unwound later. That would no longer be a tail call.

More patterns

Fibonacci with two accumulators:

ERLANG
fib(N) -> fib(N, 0, 1).

fib(0, A, _) -> A;
fib(N, A, B) when N > 0 -> fib(N - 1, B, A + B).

Counting down and printing:

ERLANG
countdown(0) -> done;
countdown(N) when N > 0 ->
    io:format("~p~n", [N]),
    countdown(N - 1).

Recursion over several structures at once, for example merging two sorted lists:

ERLANG
merge([], Ys) -> Ys;
merge(Xs, []) -> Xs;
merge([X | Xs], [Y | _] = Ys) when X =< Y -> [X | merge(Xs, Ys)];
merge(Xs, [Y | Ys]) -> [Y | merge(Xs, Ys)].

In practice you will often use lists:foldl/3, lists:map/2 and list comprehensions instead of writing recursion by hand. Writing it yourself once teaches you how those functions work, and you need it whenever the loop is not a list traversal, such as in a server.

flowchart LR
    A["sum([1,2,3], 0)"] --> B["sum([2,3], 1)"]
    B --> C["sum([3], 3)"]
    C --> D["sum([], 6)"]
    D --> E["6"]

Tail recursion with an accumulator: each call replaces the previous one.

Stand-ins in JavaScript

JavaScript engines do not guarantee tail-call optimization, so the second example uses a trampoline to show constant stack use. This is not Erlang.

JS Stand-in: accumulator recursion (JavaScript, not Erlang)

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

No output.

JS Stand-in: a trampoline runs a tail-recursive loop (JavaScript, not Erlang)

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

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the base case of recursion over a list?

    The empty list ends the recursion. [H | T] never matches it.
  2. 2. What makes a call a tail call?

    If nothing remains to be done after the call, the runtime can reuse the current frame.
  3. 3. Why is Acc ++ [X] a poor way to build an accumulator?

    Prepend with [X | Acc] and reverse at the end.
  4. 4. How does a long-running Erlang server loop forever without running out of memory?

    A tail-recursive receive loop runs in constant space.

Summary

  • Repetition is recursion: handle the base case, do one step, recurse.
  • List recursion matches [] and [H | T].
  • Body recursion uses stack proportional to depth; tail recursion with an accumulator uses constant space.
  • Prepend to accumulators with [X | Acc] and call lists:reverse/1 at the end.
  • Server loops are tail-recursive functions that never return.

Next: Funs and Higher-Order Functions