Recursion with Elixir
The strength of a language is not purely reliant on its special features, but the foundation for what it’s build on. In the case of Elixir, it’s a purely functional language; while most other languages are what we call imperative. One of the major differences between the two is that Elixir has no array structure type. Instead, Elixir implements link-lists as its choice of dynamically expanding data structures. Which brings us to an interesting cross road with how we access, modify, and apply complex logic to the data through recursion.
BASICS OF RECURSION
Let’s take a brief moment to look at what a basic concept of recursion looks like in Elixir:
Let’s now take a moment to glance visually at what’s going on in the above example.
Starting from the left, and working from the top-down, the journey begins by plucking each number off the list. Once we reach the bottom of the list we begin our journey upward. First, returning an empty list, followed by prepending the multiplied number on each return, thus creating a new list of multiplied numbers, in the order for which they were presented in.
The second part to this recursion function that might not immediately stand out, is that we are effectively conducting pattern matching. Those who have studied languages of the past will notice a very strong influence of Prolog in Elixir/Erlang. That is because Prolog pioneered the concept of parameter pattern matching and use cases of combining it with recursive functionality. A very useful feature for developing basic Artificial Intelligence applications.
Looking back at the example code, notice that we have our first function parameter as an empty list (our guard clause) while our next similar named function accepts a list with content. This means the first one is never executed unless the list is empty, and the last one is never called unless the list contains elements. And as an added bonus, none of them will run unless you supply them with a list data structure. A very common concept seen throughout all Elixir applications.
With the basics of recursion laid out, hopefully you can see that these are more or less used as loops for iterating over list types. It allows for greater flexibility for the developer in handling when and what gets executed, based on enforced pattern matching conditions.
BUILDING A BINARY SEARCH TREE
Now let’s take a peek at a slightly more in depth problem, dealing with building and inserting into a Binary Search Tree (BST).
A BST is a very simple structure for quickly accessing data and has very good portrayal to the power of recursion. The initial setup for this problem is that we need to take an ordered list of numbers to traverse and build the tree. For which recursion will aid us in creating the final result displayed in the picture above.
To build this structure, we need to follow a few simple guidelines. (leaves are represented as circles above)
- The first list element is always set as the root leaf.
- When the leaf number is greater than the number being inserted, we’ll traverse to the left side.
- When the leaf value is less than the number being inserted, we’ll traverse to the right side.
- When leaf is nil, we know we’ve reached the spot for insertion.
Following that logic, the above graph can be represented as [8,3,12,1,7], to build the tree.
Now when we try to insert a new value, we simply need to just pass the entire BST along with the value to be inserted. The ending result should be that the number 22 is inserted to the right side of 12.
Hopefully this can give some insight to the power and opportunity both recursion and pattern matching can have in a language such as Elixir. And if you find yourself with any questions over this topic, feel free to leave a comment and I’ll do my best to answer any concerns.
~George Karaszi, Software Developer
Originally published at blog.elevatorup.com.