Do you want to pick up from where you left of?
Elixir School
Presents

# Understanding Recursion with Elixir

## By Sophie DeBenedetto | Posted 2019-01-19

De-mystify the concept of recursion and gain a deeper understanding of how and why to use it by writing our very own recursive function in Elixir.

“Recursion” can be a scary word for those of us unfamiliar with its applications. In this post, we’ll de-mystify the concept of recursion and gain a deeper understanding of how and why to use it by writing our very own recursive function in Elixir.

## What is Recursion

In short, “recursion” is when a function calls itself. First we’ll look at a contrived example. Later on in this post we’ll build a more practical recursive function.

Below we’ve defined a function `RecursionPractice.hello_world/0`, that calls itself:

``````defmodule RecursionPractice do
def hello_world do
IO.puts("Hello, World!")
hello_world()
end
end``````

If you think that invoking our `RecursionPractice.hello_world/0` function would cause `"Hello, World!"` to get puts’d out to the terminal infinitely–you’re right! The `hello_world` function does two things:

1. Puts out “Hello, World!”
2. Call `hello_world/0` (again)

When `hello_world/0` is invoked again, it will do two things:

1. Puts out “Hello, World!”
2. Call `hello_world/0` (again)

And so on. While “a function that calls itself” is the basic definition of recursion, its not how we want to implement a recursive function.

Any recursive function needs a way to stop calling itself under a certain condition. This condition is often referred to as the base case. Let’s create a base case for our `RecursionPractice.hello_world/0` function. We’ll count the number of times we call the function and stop calling it once we’ve reached 10.

``````def hello_world(count \\ 0) do
IO.puts("Hello, World!")
if count < 10 do
new_count = count + 1
hello_world(new_count)
end
end``````

The `if` condition controls our recursive function for us. If the count is less than 10, increment the count by 1 and call `hello_world/1` again. Otherwise, don’t do anything, i.e. stop calling the recursive function!

We can refactor this code with the help of guard clauses. Instead of writing an `if` condition inside of our function, we’ll define another version of the `RecursionPractice.hello_world/1` function to handle our base case. This version will run when the count is greater than or equal to 10.

``````defmodule RecursionPractice do
def hello_world(count \\ 0)
def hello_world(count) when count >= 10, do: nil

def hello_world(count) do
IO.puts("Hello, World!")
new_count = count + 1
hello_world(new_count)
end
end``````

Note that we’ve moved the default argument definition into a function head. If you’re defining a function with multiple clauses and a default value, the default value definition belongs in a function head. Learn more about default arguments, function heads and function clauses in this Elixir School lesson.

## Why is it Useful?

Recursion is useful anytime we need to repeat an action under a certain condition. Anytime you want to use a `while` or `until` loop, you can probably implement your solution with recursion.

How do you decide to use a recursive approach over an iterative approach like a `while` loop? Reach for recursion when writing a recursive function produces simpler, easier to read code than a looping approach. Be careful though, if you write a recursive function without a “base case”, or stopping point, you’ll end up with a stack overflow error–you’ll call the function forever!

## Building a Recursive Function with Elixir

Now that we have a better understanding of what recursion is and how it works, let’s build a more practical recursive function.

Elixir’s `List` module provides us with a number of handy functions for operating on lists, including a `List.delete/2` function that works like this:

Given a list and an element in that list, return a new list that does not contain the fist occurrence of the given element. For example:

``````List.delete(["Apple", "Pear", "Grapefruit"], "Pear")
=> ["Apple", "Grapefruit"]``````

However, we’ll see that if the given list contains more than one appearance of `"Pear"`, `List.delete/2` only removes the first `"Pear"`

``````List.delete(["Apple", "Pear", "Grapefruit", "Pear"], "Pear")
["Apple", "Grapefruit", "Pear"]``````

What if we want to remove all occurrences of a particular element from our list? The `List` module doesn’t implement such a function. Let’s build our own!

Our desired behavior looks like this:

``````List.delete(["Apple", "Pear", "Grapefruit", "Pear"], "Pear")
["Apple", "Grapefruit"]``````

Before we start building our function, let’s take a look at how we can use recursion and pattern matching to operate on Elixir lists.

### Using Recursion on a List

Lists in Elixir are effectively linked lists, which means they are internally represented in pairs containing the head and the tail of a list. - Hex Docs

This means we can use pattern matching to grab the first element, or the “head” of the list:

``````iex> [head | tail] = [1,2,3]
1
iex> tail
[2,3]``````

Using this pattern matching approach, we can operate on each member of a list:

``````iex> list = [1,2,3,4]
[1, 2, 3, 4]
iex> [head | tail] = list
[1, 2, 3, 4]
1
iex> tail
[2, 3, 4]
iex> [head | tail] = tail
[2, 3, 4]
2
iex> tail
[3, 4]
iex> [head | tail] = tail
[3, 4]
3
iex> tail
[4]
iex> [head | tail] = tail
[4]
4
iex> tail
[]``````

Using this approach, let’s define a custom function to recurse over each element in a list. Our function will grab the `head` of the list and `puts` it out to the terminal. Then, we’ll take the `tail` and split it up into its own `head` and `tail`. We’ll keep doing this until the list is empty.

``````defmodule MyList do
def my_each([head | tail]) do
if tail != [] do
my_each(tail)
end
end
end``````

Our base case occurs when the `tail` is empty, i.e. when there are no more elements in the list. We can leverage Elixir’s ability to pattern match function arity to clean this up a bit.

Instead of implementing an `if` condition inside our recursive function, we’ll define another version of our function that will get run when `my_each` is called with an argument of an empty list. So, if `my_each` is called with an argument of a list that isn’t empty, the first version of the function will run. It will grab the `head` of the list and `puts` it out. Then it will call `my_each` again with an argument of the `tail` of the list. If and when the tail is empty, the second version of the function will run. In this case, we will not call `my_each` again.

``````defmodule MyList do
def my_each([head | tail]) do
my_each(tail)
end

def my_each([]), do: nil
end``````

Let’s see it in action:

``````iex> MyList.my_each([1,2,3,4])
1
2
3
4``````

Now that we have a handle on using recursion and pattern matching with Elixir lists, let’s get back to our recursive “delete all” function.

### Defining a Recursive `delete_all/2` Function

#### Desired Behavior

Before we start coding, let’s map out how our function needs to behave. Since Elixir is a functional language, we won’t be mutating the original list. Instead, we’ll build a new list comprised of all of the elements from the original list, minus all elements that match the element we want to exclude.

Our approach will work something like this:

• Look at the head of the list. If that element is equal to the value whose occurrences we want to remove, we will not grab the element to add to the new list.
• If that element is not equal to the value we want to remove, we will add it to the new list.
• In either case, we’ll grab the tail of the list and repeat the previous step.
• Once the tail is empty, i.e. we’ve looked at every element in the list, stop recursing.

#### Let’s Build It

First, we’ll define a `MyList.delete_all/2` function that takes in two arguments: the original list and the element whose occurrences we want to delete.

``````defmodule MyList
def delete_all(list, el) do
# coming soon!
end
end``````

However, we need access to a new, empty list that we’ll populate with the elements of the original list we’re not deleting. So, we’ll define a version of `delete_all` that takes in three arguments: the original list, the element who occurrences we want to delete, and the new empty list.

`MyList.delete_all/2` will call the `MyList.delete_all/3` function. This saves the user from having to call `delete_all` with a third argument of an empty list and allows us to provide a nice tidy API.

``````defmodule MyList
def delete_all(list, el) do
delete_all(list, el, [])
end

def delete_all([head | list], el, new_list) do
end
end``````

The `MyList.delete_all/3` function’s first job is to determine whether or not the first element in the current list, the `head` of the list, is the same value as the element we want to remove.

If so, we won’t add it to our new list. Instead, we’ll call `MyList.delete_all/3` again with the remainder of the current list, the `tail`, and pass in our `new_list` unchanged. We can accomplish this with a guard clause:

``````def delete_all([head | tail], el, new_list) when head === el do
delete_all(tail, el, new_list)
end``````

If the head of the current list is not equal to the value we want to remove, however, we do want to add it to our `new_list` before moving on.

We’ll define another `delete_all/3` function, this time without a guard clause, to meet this condition:

``````def delete_all([head | tail], el, new_list) do
delete_all(tail, el, [head | new_list])
end``````

We add the current `head` to our new list like this:

``[ head | new_list ]``

and we call `delete_all/3` again, passing it the remainder of the list (`tail`), the element to delete and the updated `new_list`.

When should we stop recursing? In other words, what is the base case that will cause us to stop calling `delete_all/3`? When we’ve recursed over all of the elements in the original list, such that the `tail` is empty, we’ll stop calling `delete_all/3` and instead return the new list. Let’s define one final `delete_all/3` function to match this condition:

``````def delete_all([], el, new_list) do
new_list
end``````

The only problem with this approach is that it builds and returns a new list in which all of the elements we kept from the original list are populated in reverse order. This is because by building out our new list like this:

``[ head | new_list ]``

We are adding the element we want to keep to the front of our new list, instead of the end.

We can fix this by using `Enum.reverse` on the `new_list` once we’ve reached our empty list base case:

``````def delete_all([], el, new_list) do
Enum.reverse(new_list)
end``````

If we put it all together, we’ll have:

``````defmodule MyList do
def delete_all(list, el) do
delete_all(list, el, [])
end

def delete_all([head | tail], el, new_list) when head === el do
delete_all(tail, el, new_list)
end

def delete_all([head | tail], el, new_list) do
delete_all(tail, el, [head | new_list])
end

def delete_all([], el, new_list) do
Enum.reverse(new_list)
end
end``````

We can even take this one step further and replace our guard clause with Elixir’s ability to pattern match function arity. Instead of using the guard clause to run a certain version of our function when `head === el`, we can write the function like this:

``````def delete_all([el | tail], el, new_list) do
delete_all(tail, el, new_list)
end``````

Now we should be able to call our function:

``````iex> MyList.delete_all(["Apple", "Pear", "Grapefruit", "Pear"], "Pear")
["Apple", "Grapefruit"]``````

And that’s it!