Recursive Functions in Elixir

I want to take some of the intimidation out of recursive functions.

The word “recursive” used to make my mind shut off the way that math terms in highschool did like “quadradic functions” or “polynomials”.

Any time I was reading something that involved recursion, I went looking somewhere else for an easier solution.

Now, I look at them as a tool that is sometimes easier to wrap my head around than digging into some of the reduce functions in the Enum module.

Ok so how can I convince you that recursive functions aren’t scary?

Let’s look at a normal function:

def normal_function(number) do
  number + 1
end

All this normal_function/1 does is accept a number and then add 1 to it.

Now let’s look at another normal function:

def also_normal(number) do
  new_number = number + 1
  other_function(new_number)
end
def other_function(number) do
  number
end

In this also_normal/1 function, we’re taking a number as an argument and adding 1 to it, and then we’re passing it as an argument to an other_function/1.

The also_normal/1 function isn’t concerned with what the other_function/1 does with the number, it just calls the function and passes in the new_number and it’s done.

Now let’s look at a (bad, infinitely looping) recursive function:

def bad_recursive_function(number) do
  new_number = number + 1
  bad_recursive_function(new_number)
end

This function is just like the also_normal/1 function in most ways: it accepts a number and adds 1 to it. Then it calls a function with the new number.

The only thing that’s different is that instead of calling a *different* function, it calls *itself* and passes in the new number.

That’s the definition of a recursive function: a function that calls itself.

If you actually ran this code (please don’t), it would run forever. Every time the function ran, it would call itself again and again with 1 added to the number each time and it would never stop adding.

To make this recursive function stop, we need another function clause:

def better_recursive_function(100) do
  100
end
def better_recursive_function(number) do
  new_number = number + 1
  better_recursive_function(new_number)
end

When we have more than one function definition and the function is called, it will try to match the arguments against each clause from top to bottom and run whichever clause matches first.

If we run better_recursive_function(100), the top clause will match and it will immediately return 100 and be done.

This top clause that stops the loop is called the “base case” or “anchor case”.

If we run better_recursive_function(98), the top clause won’t match so it will try the second clause which will match. The number 98 will have 1 added to it and better_recursive_function/1 will be called again with the new_number which is now 99.

Again, the top clause won’t match but the second will, and so the function is called one last time with a new_number of 100. The top clause matches and we’re done!

This is better, because the function can actually stop, but it’s still not safe (you’re toast if you pass in a number over 100) and it’s not very useful either.

Let’s create a contrived problem really quick and then solve it with a recursive function that’s pretty similar to our better_recursive_function/1.

Prompt:

You need a function that takes any positive integer and rounds it up to the nearest multiple of 10.

So if you pass in 41, it should return 50. If you pass in 78, you get back 80.

Solution:

First, let’s talk through how we’re going to approach the problem.

We need a “base” or “anchor” case that will stop the function from calling itself forever. Since we need to stop the loop when we have a number that’s a multiple of 10, we’ll make sure that our base case matches when we have a multiple of 10 like this:

def next_multiple_of_ten(number) when rem(number, 10) == 0 do
  number
end

Now, below the base case, we can use the same recursive function we’ve been using all along that adds 1 to the number and then calls itself again!

def next_multiple_of_ten(number) when rem(number, 10) == 0 do
  number
end
def next_multiple_of_ten(number) do
  new_number = number + 1
  next_multiple_of_ten(new_number)
end

Now we have a real (and useful!) recursive function!

Parting Thoughts

There are a lot of aspects of recursive functions that I haven’t covered.

Most of the time in day-to-day coding, you’ll reach for the functions in the Enum module when you need to create a loop of some sort.

However, recursive functions can be the best tool for the job when you’ve got to keep track of a few different variables as you go through a loop, and even though we didn’t cover any examples of that here hopefully this provides a foundation so that the more complex examples elsewhere will make sense.

I find myself using recursive functions a lot in coding interview type questions, and not a lot in actual projects. Your experience may be different!

If you want to dig a little deeper into how recursive functions work (now that they’re not intimidating anymore!), check out the following resources:

• Official Guides
• Programming Elixir 1.6 (I highly recommend this book)
• Elixir School
• A quick Google search for “Elixir recursive function”

Thanks for reading!