9 Recursion¶
{% include toc.html %}
9.1 Loops through recursion¶
Due to immutability, loops in Elixir (and in any functional programming language) are written differently from imperative languages. For example, in an imperative language (like C in the following example), one would write:
for(i = 0; i < array.length; i++) {
array[i] = array[i] * 2
}
In the example above, we are mutating both the array and the variable
i
. Mutating is not possible in Elixir. Instead, functional languages
rely on recursion: a function is called recursively until a condition is
reached that stops the recursive action from continuing. No data is
mutated in this process. Consider the example below that prints a string
an arbitrary amount of times:
defmodule Recursion do
def print_multiple_times(msg, n) when n <= 1 do
IO.puts msg
end
def print_multiple_times(msg, n) do
IO.puts msg
print_multiple_times(msg, n - 1)
end
end
Recursion.print_multiple_times("Hello!", 3)
# Hello!
# Hello!
# Hello!
Similar to case
, a function may have many clauses. A particular
clause is executed when the arguments passed to the function match the
clause’s argument patterns and its guard evaluates to true
.
When print_multiple_times/2
is initially called in the example
above, the argument n
is equal to 3
.
The first clause has a guard which says “use this definition if and only
if n
is less than or equal to 1
”. Since this is not the case,
Elixir proceeds to the next clause’s definition.
The second definition matches the pattern and has no guard so it will be
executed. It first prints our msg
and then calls itself passing
n - 1
(2
) as the second argument.
Our msg
is printed and print_multiple_times/2
is called again
this time with the second argument set to 1
. Because n
is now
set to 1
, the guard in our first definition of
print_multiple_times/2
evaluates to true, and we execute this
particular definition. The msg
is printed, and there is nothing left
to execute.
We defined print_multiple_times/2
so that no matter what number is
passed as the second argument it either triggers our first definition
(known as a “base case”) or it triggers our second definition which will
ensure that we get exactly one step closer to our base case.
9.2 “Reduce” and “map” algorithms¶
Let’s now see how we can use the power of recursion to sum a list of numbers:
defmodule Math do
def sum_list([head|tail], accumulator) do
sum_list(tail, head + accumulator)
end
def sum_list([], accumulator) do
accumulator
end
end
Math.sum_list([1, 2, 3], 0) #=> 6
We invoke sum_list
with the list [1, 2, 3]
and the initial value
0
as arguments. We will try each clause until we find one that
matches according to the pattern matching rules. In this case, the list
[1, 2, 3]
matches against [head|tail]
which bounds head
to
1
and tail
to [2, 3]
; accumulator
is set to 0
.
Then, we add the head of the list to the accumulator
head + accumulator
and call sum_list
again, recursively, passing
the tail of the list as its first argument. The tail will once again
match [head|tail]
until the list is empty, as seen below:
sum_list [1, 2, 3], 0
sum_list [2, 3], 1
sum_list [3], 3
sum_list [], 6
When the list is empty, it will match the final clause which returns the
final result of 6
.
The process of taking a list and “reducing” it down to one value is known as a “reduce” algorithm and is central to functional programming.
What if we instead want to double all of the values in our list?
defmodule Math do
def double_each([head|tail]) do
[head * 2|double_each(tail)]
end
def double_each([]) do
[]
end
end
Math.double_each([1, 2, 3]) #=> [2, 4, 6]
Here we have used recursion to traverse a list doubling each element and returning a new list. The process of taking a list and “mapping” over it is known as a “map” algorithm.
Recursion and tail call optimization are an important part of Elixir and are commonly used to create loops. However, when programming in Elixir you will rarely use recursion as above to manipulate lists.
The `Enum
module </docs/stable/elixir/Enum.html>`__, which we’re
going to see in the next chapter, already provides many conveniences for
working with lists. For instance, the examples above could be written
as:
iex> Enum.reduce([1, 2, 3], 0, fn(x, acc) -> x + acc end)
6
iex> Enum.map([1, 2, 3], fn(x) -> x * 2 end)
[2, 4, 6]
Or, using the capture syntax:
iex> Enum.reduce([1, 2, 3], 0, &+/2)
6
iex> Enum.map([1, 2, 3], &(&1 * 2))
[2, 4, 6]
Let’s take a deeper look at Enumerable
s and, while we’re at it,
their lazy counterpart, Stream
s.