Back to Posts

Recursively iterating in the wild with Elixir

Nikola Novakovic in Code

Hey peeps!

It's been a while since I wrote a technical blog post, so here goes one on Elixir and recursion.

Before we do anything we need to understand the terminology, so what is recursion ?

From Wikipedia:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).

That's a pretty wide and abstract explanation, so let's try to explain it more with good ol' plain English:

The calling of a function from within that same function.

Now that's not that scary isn't it? :)

Recursion is implemented in a lot of mainstream languages ( Java, Python, Ruby ) but I've been playing a lot with it in Elixir.

Next thing that we need to know is when and why to use recursion to iterate over something ?

  • It's more clean and easier to read then a classic for loop

  • It's less error prone

  • It's usually less code to achieve the same thing as you would with classic iteration

  • Generally If you are writing code in a functional programming language recursion is much cheaper and faster ( in terms of resources ). On the other hand if you are writing code in Java it's the other way around.

Regarding the last bullet point there is a lot of CS material out there that goes into depth on why this is true. Also you'll find recursion mentioned with terms such as Binary Trees and Binary Search Trees and if we go deeper into that direction it can turn this post into a book but let's not go down that route. ( that doesn't mean you should not google it and learn about it, it's pretty interesting )

Finally it's time for some examples.

Let's write a module MyList in which we will implement two functions to manipulate lists.

First let's write a function that takes in a list of numbers and returns a new list with squares of each of those numbers.

defmodule MyList do

 def square([]) do
   []
 end

 def square([ head | tail ]) do
   [ head * head | square(tail) ]
 end

end  

A couple of things are happening here. First we see two functions that are named the same way, that's because Elixir can pattern match against arguments of functions and call an appropriate one. Param in the second function is expecting a list and it's "splitting" up that list into it's head (first param) and tail ( the rest ). If you want to learn more on that I wrote about it here and here.

Let's see some CLI action:

$ iex my_list.exs

iex > MyList.square([3, 4, 5])

# => [ 9, 16, 25 ] 

Yay, it works! But how is that working actually ?

Well let's break it up a bit:

# first time when calling square it pattern matches
# against the second square function

[ 3*3 | square([4, 5]) ]

# In the next iteration it again matches with the same function

[ 4*4 | square([5]) ]

# and this keeps repeating until it matches the [] version of square. At that point it calculates the results

Elixir uses closures to help with calculating the final list and that's a blog post on it's own, but hopefully the basics of how it's done are clear.

Ok let's add one more example. Let's implement map function. It's a pretty famous function in the functional programming world, it takes a list and a function and returns a new list where that function is applied to each member of the list.

def map([], _func) do  
  []
end

def map([head | tail], func) do  
  [ func.(head) | map(tail, func) ]
end

It's actually similar to our square function but with the difference of func.(head). That's a way in Elixir to call an anonymous function.

Let's try it out in the CLI again:

iex > MyList.map([1, 2, 3], fn(n) -> n + 1 end)

# => [2, 3, 4]

For exercise you can write on paper how this actually works and steps taken to get to the result.

Well that's all folks. I am going to publish a second part of this post where we are going to cover different types of recursions and how to protect yourself from infinite recursion calls.

Hope you enjoyed this one, feedback is always welcome over all of the mediums on the interwebz.

Software engineer that loves business side of things as well. Also lifts a lot of weights.

Read Next

Guide on how to survive a storm