Recursion

Erlang has no loops — iteration is recursion (or library functions).

Erlang has no loops — iteration is recursion (or library functions).

9.1 Basic recursion

-module(rec).
-export([factorial/1, len/1, sum/1, fib/1]).

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

len([]) -> 0;
len([_ | T]) -> 1 + len(T).

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

fib(0) -> 0;
fib(1) -> 1;
fib(N) when N > 1 -> fib(N - 1) + fib(N - 2).

9.2 Tail recursion with accumulators

Tail calls run in constant stack space. Essential for infinite loops (server processes). For list-building, body recursion is often just as fast on modern BEAM (see the Efficiency Guide's "seven myths").

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

reverse(L) -> reverse(L, []).
reverse([], Acc) -> Acc;
reverse([H | T], Acc) -> reverse(T, [H | Acc]).

9.3 Helper functions with different arity

Common idiom: public f/1 calls private f/2 with an accumulator. Since f/1 and f/2 are different functions, only export the one you need.

9.4 Recursion over trees

%% Tree = nil | {node, Left, Value, Right}
insert(V, nil) -> {node, nil, V, nil};
insert(V, {node, L, X, R}) when V < X -> {node, insert(V, L), X, R};
insert(V, {node, L, X, R}) when V > X -> {node, L, X, insert(V, R)};
insert(_, T) -> T.

to_list(nil) -> [];
to_list({node, L, V, R}) -> to_list(L) ++ [V] ++ to_list(R).