18 Feb /Recursion in Elixir

Coming from an object oriented language with data mutability, learning looping in Elixir required that I let go of my current understanding about iterating over a collection. In fact, just forget looping and think recursion. So, what’s recursion?

Recursion is solving a problem whereby one applies the same solution to smaller instances of that problem. Think, a function calling itself. So, here is what it looks like in Elixir:

defmodule Recursionism do

  def operate_on_list_items([], _) do
    []
  end

  def operate_on_list_itmes([head | tail], fun) do
    [fun.(head) | operate_on_list_items(tail, fun)]
  end
end

Recursionism.operate_on_list_items([1, 2, 3], fn(n) -> n * n end)

Let’s break this down:

• First we define a multi-clause function called Recusionism.operate_on_list/2. Multi-cause functions are multiple functions of the same name and arity that are executed depending on the matching of the arguments.
• Then, when we call Recusionism.operate_on_list_items([1, 2, 3], fn(n) -> n * n end), it matches the second multi-clause function definition and executes it.
• That second function, uses the anonymous function (it’s second argument) to operate on the first item in the list (head). The result of applying the anonymous function (fun.(head)) becomes the first item in a new list.
• In order to complete the list, the operate_on_list_items function calls itself by passing all the remaining items in the original list (tail) as the first argument, along with the same anonymous function as the second argument.
• When there are no more items in the list, calling operate_on_list_items matches the first multi-clause function definition and returns an empty list, thereby stopping the recursion.
• The end result is building a list by doing [1 | [4 | [9 | []]]], which evaluates to [1, 4, 9]