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.

count(0) -> done;

done

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.

count(3).

3

2

1

done

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.

sum([]) -> 0;

0

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.

sum([1, 2, 3]).

6

Next: Lists

Article author: Arthur Isaev