Recursion

Recursion is an important concept to master when writing in any functional programming language. In the context of computer science, the word recursive is defined as, "a procedure that reinvokes itself upon completion". A recursive function is one that will execute some code and then call itself to run again. If this sounds like a "loop" to you, you're absolutely right.

Since a function that ends with a call to itself forms a loop, we'll eventually need some way to exit the loop. This is known as the ending condition or base case. The base case is usually the first line in a recursive function. This way, each iteration of the function must first check if the base case is satisfied. If it is the function exits. Otherwise, the function continues on and calls itself again at the end. Let's look at a simple example to better understand recursion in action.

Our goal is to print each element in a list one by one. We will utilize the hd and tl functions. If you aren't familiar with Elixir lists, refer back to the Collections chapter.

First, we'll create a list of strings.

list = ["this", "is", "a", "list", "of", "strings"]

Next, we'll define two variations of the print function. The first variation pattern matches an empty list. The second pattern matches a non-empty list.

list = ["this", "is", "a", "list", "of", "strings"]
defmodule PrintList do

  def print([]) do
  end

  def print([head | tail)] do
   IO.puts(head)
   print(tail)
  end

end

The first definition of print pattern matches on an empty list. The function doesn't do anything, notice how the body of the function is empty. This is going to be the base case. It's the equivalent of saying, "if we have an empty list then we're done processing". The next definition of print takes a list as an argument, separating the list by its "head" and "tail". It prints the head (the first element) to the console and passes the tail to the print function.

If there was only one element in the list then the list would be empty after the first iteration. When print is called with an empty list it will match the first definition, bringing the function to an end. If there were more items in the list, the second definition will be invoked, printing the next element to the console and calling print on the remaining elements. This function continues printing one element at a time recursively until the list is exhausted. Here is the result of passing our "list" to the print function:

iex> PrintList.print(list)
"this"
"is"
"a"
"list"
"of"
"strings"

Tail call Optimization

Erlang will automatically optimize your code if your recursive function ends in a tail call. If a recursive function ends with a call to another function, it can be "tail call optimized". This means the Erlang VM does not need to allocate additional memory for the recursing function and can therefore significantly upgrade the performance of the code. It is important to remember the function must end with another function call and not an operation, such as incrementing or decrementing a value.