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.

  1. Which loop keywords does Erlang have?

    Answer

    None: repetition is recursion

    The language has no loop statement; a function that calls itself repeats work.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. What does sum([]) return in the mysum module?

    Answer

    0

    The empty list has nothing to add, so the base case answers zero.

  9. 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.

  10. What does the base case of countdown:count/1 print?

    Answer

    done

    The countdown prints 3, 2, 1, then the base case prints done and the call returns ok.

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