Elixir — A Tincture for Functional Programming Part 1.5 Recursion

Recursion

Why Recursion is important in Elixir

Recursion is important in Elixir because we cannot mutate the state of any values in Elixir.This means that any operation that requires repetition and mutating a value, is not viable in Elixir.

These examples are not possible in Elixir, as written, because they depend on the variables being mutated. For Elixir, we need to turn to recursion if we want to achieve similar repetitive tasks.

Note: Elixir does provide the use of comprehensions, which are an added piece of syntactical sugar to create code block similar to the for x in collection style of repetition. This is just syntactical sugar (albeit very handy syntactical sugar) and there is no variable mutation occurring under the hood. So, bearing that in mind we’ll focus on the recursive solutions herein as they are a hallmark of Functional Programming.

Making Sure It Stops

Recursion in Elixir is no different than recursion in any other programming language in that it is critically important to identify the case which will bring the recursive call to an end.

Without this end clause, stack overflows and CTRL+Cawaits you.

The ending function clause needs to be defined before the other clauses, because Elixir will execute the first matching function clause that it finds for a function definition (remember short circuiting).

Where Recursion Shines in Elixir — Lists

One of the most useful uses of recursion in Elixir, is the iteration, transformation, and selection of lists.

All based on the use of [head | tail]to extract the head node of the current list, act on it and pass the tail (see: the remaining list nodes) to a recursive function call. We can leverage the syntax feature of creating new lists by using this same [head |tail] syntax to append a new node onto a list (which is faster than appending to the list).

[:a | [:b, :c, :d] ~~~> [:a, :b, :c, :d]

Iteration:

Here we can see how we can construct a basic set of functions show_cheese to iterate through all the nodes of a list (and print to the screen just for demo purposes).

Transformation:

If we want to transform each element in the list, we can also do that with our change_cheese functions. The key here is to return a new list that leverages the recursive function call within the return value.

Selection:

To return a new list that only contains values that match some set of criteria we provide, we can do that as well with one extra conditional block. select_cheese shows how we can do this pretty easily.

Modules to the Rescue

Now that we have covered how to create basic iteration, transformation, and selection methods for lists, I’ll share a secret:

There are built in modules in Elixir that abstract away the need to hard code this functionality yourself!

The Enum module in Elixir contains methods that can accomplish these operations, plus a host of other useful ones as well, so before you go reinventing the wheel, make sure that operation is not already covered!

Conclusion

There are other features of recursion in Elixir like tail-call optimization and work with streams that I may tackle later, but don’t be afraid to start working through recursion on your own!