Recursion replaces loops
Base case first
Erlang has no for or while loop. Repetition is a function that calls itself, and every such function starts with its base case, the input small enough to answer directly.
Write the base case before the recursive step, so the function always has a way to stop. Save this module as countdown.erl.
-module(countdown).
-export([count/1]).
count(0) ->
io:format("done~n");
count(N) ->
io:format("~p~n", [N]),
count(N - 1).
One step
The recursive step moves the input one unit toward the base case. Each call works on a smaller problem, and the calls stop when the base case matches.
A missing base case is an infinite call chain, which ends in a stack error that names the offending function.
erlc countdown.erl
erl
1> countdown:count(3).
3
2
1
done
ok
Tail recursion
A call is in tail position when it is the last thing the function does. Tail calls reuse the stack frame, so a tail recursive function runs in constant memory.
The trick is an accumulator: carry the partial result in an extra argument, and hand it to the next call. Save this module as mysum.erl.
-module(mysum).
-export([sum/1, sum_acc/2]).
sum([]) -> 0;
sum([H|T]) -> H + sum(T).
sum_acc([], Acc) -> Acc;
sum_acc([H|T], Acc) -> sum_acc(T, Acc + H).
A real example
Here is the whole pattern in one function: base case answers zero, and the step adds the head and recurses on the tail.
The accumulator version returns the same answer with a flat call stack, which is the house style for long loops.
erlc mysum.erl
erl
1> mysum:sum([1, 2, 3]).
6
2> mysum:sum_acc([1, 2, 3], 0).
6
Next: Lists
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Which loop keywords does Erlang have?
Answer
None: repetition is recursion
The language has no loop statement; a function that calls itself repeats work.
-
What does every recursive function need first?
Answer
A base case
The base case answers the smallest input directly, so the recursion has a place to stop.
-
What does the recursive step do?
Answer
Calls the function with a smaller problem
Each call moves one step toward the base case, so the chain of calls is finite.
-
What happens to a recursive function with no base case?
Answer
It runs forever until the stack fails
Nothing stops the calls, so the runtime eventually reports a stack error.
-
In
count(N) -> io:format("~p~n", [N]), count(N - 1)., what form does the last call have?Answer
It is a tail call
The recursive call is the last expression of the clause, so it is in tail position.
-
Why does a tail call save memory?
Answer
It reuses the current stack frame
The runtime does not keep the caller frame, so a long loop runs in constant stack space.
-
What is the accumulator in
sum_acc/2?Answer
The extra argument that carries the partial result
The second argument holds the running total and becomes the answer when the list is empty.
-
What does
sum([])return in the mysum module?Answer
0The empty list has nothing to add, so the base case answers zero.
-
Which clause matches a non-empty list?
Answer
sum([H|T]) -> H + sum(T).[H|T]splits the list into its head and tail, and the body adds the head to the sum of the tail. -
What does the base case of
countdown:count/1print?Answer
doneThe countdown prints 3, 2, 1, then the base case prints
doneand the call returnsok.
The examples on this page were compiled and run with Erlang/OTP 27 (erts-15.2.7.14) on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev