Recursion

In this lesson, we’ll explore one of the most fundamental concepts in functional programming: recursion. This is how Erlang handles repetition and processes data structures like lists and trees.

Understanding Recursion

In programming, recursion breaks big problems into smaller, similar problems until we reach a simple case we can solve directly.

Your First Recursive Function

Let’s start a simple example of counting down from a number:

% Start the Erlang shell
$ erl

% Define a countdown function
1> countdown(0) ->
1>     io:format("Blast off!~n");
1> countdown(N) ->
1>     io:format("~p~n", [N]),
1>     countdown(N - 1).

% Try it out
2> countdown(5).
5
4
3
2
1
Blast off!

Let’s break this down step by step:

1. Base case: countdown(0) prints “Blast off!” and stops
2. Recursive case: countdown(N) prints N, then calls itself with N-1
3. Progress: Each call gets us closer to the base case

This pattern (base case plus recursive case) is the foundation of all recursive functions.

The Anatomy of Recursion

Every recursive function needs three key components:

1. Base Case

The condition that stops the recursion. Without this, your function would run forever!

2. Recursive Case

The part where the function calls itself with modified parameters.

3. Progress Toward Base Case

Each recursive call must get closer to the base case.

Let’s see this in a simple example:

% Count down from any number
3> count_down(0) ->
3>     io:format("Done!~n");  % Base case
3> count_down(N) when N > 0 ->  % Recursive case with guard
3>     io:format("~p~n", [N]),
3>     count_down(N - 1).      % Progress: N gets smaller

Processing Lists with Recursion

Now let’s apply recursion to something more practical: processing lists. In Erlang, we typically process lists by handling the head (first element) and recursively processing the tail (rest of the list).

Counting List Elements

% Count the number of elements in a list
4> CountList = fun
4>     ([]) -> 0;  % Base case: empty list has 0 elements
4>     ([_Head | Tail]) -> 1 + CountList(Tail)  % Recursive case
4> end.

5> CountList([1, 2, 3, 4, 5]).
5

6> CountList([]).
0

7> CountList([hello, world]).
2

Let’s trace through CountList([1, 2, 3]):

1. CountList([1, 2, 3]) → 1 + CountList([2, 3])
2. CountList([2, 3]) → 1 + CountList([3])
3. CountList([3]) → 1 + CountList([])
4. CountList([]) → 0
5. Working backwards: 1 + (1 + (1 + 0)) = 3

Finding the Sum of Numbers

% Sum all numbers in a list
8> SumList = fun
8>     ([]) -> 0;  % Base case: empty list sums to 0
8>     ([Head | Tail]) -> Head + SumList(Tail)  % Add head to sum of tail
8> end.

9> SumList([1, 2, 3, 4, 5]).
15

10> SumList([10, 20, 30]).
60

Building New Lists

A common pattern is building a new list by transforming each element of an existing list:

% Double every number in a list
11> DoubleList = fun
11>     ([]) -> [];  % Base case: empty list returns empty list
11>     ([Head | Tail]) -> [Head * 2 | DoubleList(Tail)]  % Double head, recurse on tail
11> end.

12> DoubleList([1, 2, 3, 4]).
[2, 4, 6, 8]

% Convert numbers to strings
13> NumbersToStrings = fun
13>     ([]) -> [];
13>     ([Head | Tail]) -> [integer_to_list(Head) | NumbersToStrings(Tail)]
13> end.

14> NumbersToStrings([1, 2, 3]).
["1", "2", "3"]

Notice the pattern: [ProcessedHead | ProcessedTail]. This is how we build new lists in Erlang.

Important Note: Anonymous Functions and Self-Reference

You might be tempted to write recursive anonymous functions like this:

% This WON'T work!
Countdown = fun(0) ->
    io:format("Done!~n");
(N) ->
    io:format("~p~n", [N]),
    Countdown(N - 1)  % Error: Countdown is not yet bound!
end.

This doesn’t work because the variable Countdown isn’t bound until the entire anonymous function expression is evaluated. The function can’t reference itself by name during its own definition.

Solution: Use named functions instead:

% This works!
countdown(0) ->
    io:format("Done!~n");
countdown(N) ->
    io:format("~p~n", [N]),
    countdown(N - 1).

The examples in this lesson use named functions for recursive cases to avoid this common pitfall. Anonymous functions work great when they don’t need to call themselves, like the list processing functions we saw earlier.

Tail Recursion: An Important Optimization

The recursive functions we’ve written so far accumulate work as they recurse. A more efficient approach is tail recursion, where the recursive call is the last operation.

What Makes a Call “Tail Recursive”?

A function is tail recursive when the recursive call is the very last thing that happens before returning. This means no additional computation happens after the recursive call returns. When Erlang sees this pattern, it can optimize by reusing the current stack frame instead of creating a new one for each call. This optimization is called tail call optimization (TCO).

Understanding the Problem

Let’s look at our sum function again:

SumList([1, 2, 3]) →
  1 + SumList([2, 3]) →
  1 + (2 + SumList([3])) →
  1 + (2 + (3 + SumList([]))) →
  1 + (2 + (3 + 0)) →
  1 + (2 + 3) →
  1 + 5 →
  6

Each recursive call must wait for the result of the next call. This uses stack space for each call.

Notice the 1 + SumList([2, 3]) pattern: the addition happens AFTER the recursive call returns. This is NOT tail recursive because we still have work to do (the addition) after the recursive call completes.

The Tail Recursive Solution

With tail recursion, we use an accumulator to build up the result:

% Tail-recursive version with accumulator
15> sum_list_tail([], Acc) ->
15>     Acc;  % Base case: return accumulator
15> sum_list_tail([Head | Tail], Acc) ->
15>     sum_list_tail(Tail, Acc + Head).  % Add to accumulator

% Helper function to start with accumulator = 0
16> sum_list_2(List) -> sum_list_tail(List, 0).

17> sum_list_2([1, 2, 3, 4, 5]).
15

Let’s trace through sum_list_2([1, 2, 3]):

1. sum_list_tail([1, 2, 3], 0) → sum_list_tail([2, 3], 1)
2. sum_list_tail([2, 3], 1) → sum_list_tail([3], 3)
3. sum_list_tail([3], 3) → sum_list_tail([], 6)
4. sum_list_tail([], 6) → 6

No waiting! Each call can immediately call the next with the updated accumulator.

Why This Matters

The key difference:

• Non-tail recursive: Head + SumList(Tail) - must wait for SumList to return before adding
• Tail recursive: SumListTail(Tail, Acc + Head) - the recursive call IS the return value

With tail recursion, Erlang can optimize by:

1. Reusing the same stack frame for each call
2. Converting recursion into a loop internally
3. Handling millions of iterations without stack overflow

This makes tail recursion essential for processing large data sets or implementing long-running server loops.

More Tail Recursive Examples

% Tail-recursive list reversal
18> reverse_list([], Acc) ->
18>     Acc;
18> reverse_list([Head | Tail], Acc) ->
18>     reverse_list(Tail, [Head | Acc]).

19> reverse_list([1, 2, 3, 4], []).
[4, 3, 2, 1]

% Tail-recursive factorial
20> factorial(0, Acc) ->
20>     Acc;
20> factorial(N, Acc) ->
20>     factorial(N - 1, N * Acc).

21> factorial(5, 1).
120

Practical Example: Message Processing

Let’s apply recursion to our chat server by building a message processing system:

% Define a message record structure
22> Message = fun(User, Text, Timestamp) ->
22>     {message, User, Text, Timestamp}
22> end.

% Create some sample messages
23> Messages = [
23>     Message("alice", "Hello everyone!", 1609459200),
23>     Message("bob", "Hi Alice!", 1609459260),
23>     Message("alice", "How is everyone doing?", 1609459320),
23>     Message("charlie", "Great! Thanks for asking.", 1609459380)
23> ].

% Count messages from a specific user
24> count_user_messages([], _User, Count) ->
24>     Count;
24> count_user_messages([{message, User, _, _} | Tail], User, Count) ->
24>     count_user_messages(Tail, User, Count + 1);
24> count_user_messages([_Message | Tail], User, Count) ->
24>     count_user_messages(Tail, User, Count).

25> count_user_messages(Messages, "alice", 0).
2

% Extract all usernames
26> extract_users([]) ->
26>     [];
26> extract_users([{message, User, _, _} | Tail]) ->
26>     [User | extract_users(Tail)].

27> extract_users(Messages).
["alice", "bob", "alice", "charlie"]

Building a Message Filter

% Filter messages from a specific user
28> filter_user_messages([], _User) ->
28>     [];
28> filter_user_messages([{message, User, _, _} = Message | Tail], User) ->
28>     [Message | filter_user_messages(Tail, User)];
28> filter_user_messages([_Message | Tail], User) ->
28>     filter_user_messages(Tail, User).

29> filter_user_messages(Messages, "alice").
[{message, "alice", "Hello everyone!", 1609459200},
 {message, "alice", "How is everyone doing?", 1609459320}]

Common Recursive Patterns

Here are the most common patterns you’ll use:

1. List Processing (Simple)

ProcessList = fun
    ([]) -> BaseValue;
    ([Head | Tail]) -> ProcessElement(Head, ProcessList(Tail))
end.

2. List Processing (Tail Recursive)

ProcessListTail = fun
    ([], Acc) -> Acc;
    ([Head | Tail], Acc) ->
        NewAcc = UpdateAccumulator(Head, Acc),
        ProcessListTail(Tail, NewAcc)
end.

3. List Building

BuildList = fun
    ([]) -> [];
    ([Head | Tail]) -> [TransformElement(Head) | BuildList(Tail)]
end.

4. List Filtering

FilterList = fun
    ([]) -> [];
    ([Head | Tail]) ->
        case ConditionMet(Head) of
            true -> [Head | FilterList(Tail)];
            false -> FilterList(Tail)
        end
end.

When to Use Recursion

Recursion is ideal when:

1. Processing lists: Most list operations in Erlang use recursion
2. Tree traversal: Navigating hierarchical data structures
3. Divide and conquer: Breaking problems into smaller pieces
4. Mathematical sequences: Factorial, Fibonacci, etc.
5. Parsing: Breaking down complex input step by step

Key Takeaways

1. Every recursive function needs a base case to stop the recursion
2. Each recursive call must make progress toward the base case
3. Tail recursion is more memory-efficient than simple recursion
4. Use accumulators to convert simple recursion to tail recursion
5. Pattern matching with head/tail is the standard way to process lists
6. Recursion is fundamental to functional programming in Erlang

Next Steps

In the next lesson, we’ll explore higher-order functions like map, filter, and fold. These powerful functions use recursion internally but provide a more declarative way to process data.

The recursive thinking you’ve learned here is fundamental to Erlang programming. As we progress, you’ll see how recursion naturally extends to process-based programming and distributed systems.