Cover by Francesco Cesarini, Simon Thompson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

Recursion

The best way to tackle programming problems is to use the well-tested strategy of divide and conquer to break the problem into a number of simpler subproblems. By joining together the solutions of several simple problems, you solve the bigger one without even realizing it! Let’s try this approach by taking a list of integers and adding 1 to every element in the list. Because Erlang is a single assignment language, we have to create a new list, in which we will store the result.

We will name the function bump/1 and divide the problems into smaller tasks that are easier to solve, implementing one clause at a time. If the old list is empty, the new one should also be empty. The following function clause takes care of this case:

bump([]) -> [];

The second possibility is that the list contains at least one element. If so, we split the list to a head and a tail. We take the head and create a new list whose head is the head of the old list incremented by 1:

bump([Head | Tail]) -> [Head + 1 | ?].

Now, the question is how do we proceed with the rest of list? We want to construct a new list where all the elements are one larger than in the old list. But that is exactly what the bump function is supposed to do! The solution is to call the function we are defining recursively using the tail of the list:

bump([Head | Tail]) -> [Head + 1 | bump(Tail)].

This provides us with what we are looking for. We recurse on the tail, and ensure that bump/1 returns a well-formed list that can be the tail ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required