Looping with Recursion

When people newly come to Elixir, it is common to struggle with doing “basic” things like looping. “Looping” is when you want to perform an action a number of times or you want to perform an action on each item in a list. This really is a fundamental need in programming!

The problem people encounter is that the familiar tools and patterns they are comfortable with aren’t available in Elixir. Of course this doesn’t mean you can’t accomplish the your goal, it just means you need to learn some new ways to do it. You need a new way to think about it.

Recursive Functions

Let’s briefly define what a Recursive Function is:

A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result at the end of each iteration.

https://techterms.com/definition/recursivefunction

A recursive function is one that calls itself. Recursion, combined with pattern matching and other features of the BEAM enable for some powerful abilities and looping is one of them.

Revisiting the for loop

Functional Programming languages don’t have the common for loop you are likely familiar with. Here’s an example of a Javascript for loop.

var data = [1, 2, 3, 4, 5];

for (var i = 0; i < data.length; i++) {
  console.log(`Value of data[${i}] =`, data[i]);
}

After running this in a browser, the console shows this output:

Value of data[0] = 1
Value of data[1] = 2
Value of data[2] = 3
Value of data[3] = 4
Value of data[4] = 5

Writing a for loop like this isn’t allowed in functional languages because each iteration is mutating the variable i. Functional languages have immutable data so right away this construct isn’t allowed.

How do we then solve problems in Elixir where we need to “loop”? Elixir has some great convenience functions available to help us solve “looping” problems and we will cover them. Before we talk about the shortcuts available, let’s talk about how it fundamentally works. Understanding the fundamentals is important because it gives you confidence in the system and the principles are central to how more advanced features and behaviors work.

Recursively processing a list

Let’s convert that Javascript example into an Elixir one and see how it works. We want to write a function that can process a list of numbers and print to the console the value of the number. Using pattern matching, I can pull off the first number of the list num and get the rest of the list in rest. Ex: [num | rest]. This works! Almost…

defmodule Playing do
  def process([num | rest]) do
    IO.puts "Value of num = #{num}"
    process(rest)
  end
end

data = [1, 2, 3, 4, 5]
Playing.process(data)
#=> Value of num = 1
#=> Value of num = 2
#=> Value of num = 3
#=> Value of num = 4
#=> Value of num = 5
#=> ** (FunctionClauseError) no function clause matching in Playing.process/1    
#=>     
#=>     The following arguments were given to Playing.process/1: 
#=>     
#=>         # 1
#=>         []

It correctly prints out all the numbers but then fails with a function clause matching error when it gets to an empty list. Because [] does not match the pattern[num | rest]. The fix is to add the second clause that matches an empty list.

defmodule Playing do
  def process([num | rest]) do
    IO.puts "Value of num = #{num}"
    process(rest)
  end

  def process([]), do: "Done!"
end

data = [1, 2, 3, 4, 5]
Playing.process(data)
#=> Value of num = 1
#=> Value of num = 2
#=> Value of num = 3
#=> Value of num = 4
#=> Value of num = 5
#=> "Done!"

Now it works correctly! It processes the first item in a list and passes on the remaining items to be processed the same way. It matches when there are no items left to process and stops.

Right now, the final return is the string "Done!". That "Done!" clause can be helpful when we want to return a computed result. Let’s change the function to instead sum all the numbers in the list and see how that works.

Summing a list

To get a more complete view of how this works, let’s look at how we could sum a list of numbers in Javascript first.

function sum(list) {
  var acc = 0;
  for (var i = 0; i < data.length; i++) {
    acc = acc + data[i];
  }
  return acc;
}

var data = [1, 2, 3, 4, 5];
sum(data);
//=> 15

In Javascript we declare a variable to accumulate the sum of values as we go. We will call this accumulator acc and it starts with a value of 0. The for loop mutates both the i counter and the acc accumulator as it runs. After the loop completes, we have our total stored in acc and finally return acc as the answer.

How can we do that in Elixir without mutating variables?

defmodule Playing do
  def sum([num | rest], acc) do
    sum(rest, acc + num)
  end

  def sum([], acc), do: acc
end

data = [1, 2, 3, 4, 5]
Playing.sum(data, 0)
#=> 15

The Elixir version has all the same parts as the Javascript version, just arranged differently. The most important change is that variables are never mutated!

A side-by-side comparison will help solidify this point.

Pattern matching tells us when we should stop recursively calling sum and return the accumulator.

Thinking Tip

To recursively loop in Elixir we need 2 function clauses. One that does the iteration work and another to tell us when we are done. Pattern matching works perfectly for this. Also, if you want to accumulate a value in the process, you add arguments to pass it along.

Example of the 2 function clauses using pattern matching needed for looping:

def process([item | rest]) do
  # do work
  process(rest)
end

def process([]) do
  # we are done
end

A while Equivalent

A while loop is also a common feature in imperative languages. Like the for loop, this isn’t allowed in functional languages, and similarly it isn’t needed. Let’s look at what makes a while loop.

while (condition) {
  // code block to be executed
}

While some condition remains true, execute the code inside the while block.

Let’s create a Javascript example and convert it to Elixir to see how it compares. This defines a build_text function. You pass in the number of lines to generate and it returns a string with that number of lines added.

Like the for loop, it mutates a looping counter num and builds up a text variable to be returned as the result.

function build_text(number) {
    var num = 0;
    var text = "";

    while (num < number) {
        text += `Processed number ${num}\n`;
        num++;
    }
    return text;
}

build_text(5)
#=> "Processed number 0
#=> Processed number 1
#=> Processed number 2
#=> Processed number 3
#=> Processed number 4
#=> "

Let’s see how this can be done in Elixir.

defmodule Playing do
  def build_text(number) do
    do_build_text(number, 0, "")  
  end
  
  defp do_build_text(total, num, text) when num < total do
    do_build_text(total, num + 1, text <> "Processed number #{num}\n")
  end
  
  defp do_build_text(_total, _num, text), do: text
end

text = Playing.build_text(5)
#=> "Processed number 0\nProcessed number 1\nProcessed number 2\nProcessed number 3\nProcessed number 4\n"

IO.puts text
#=> Processed number 0
#=> Processed number 1
#=> Processed number 2
#=> Processed number 3
#=> Processed number 4

Wow! This one looks a little different! We have some fun things to talk about here.

• The first is that our build_text/1 function declaration looks just like the Javascript one, meaning that the API for the function is the same.
• Remember that to do recursive looping functions in Elixir we need at least 2 function clauses? These are the do_build_text/3 function clauses.
• The do_ prefix is an Elixir naming convention for this pattern. Specifically, the do_ prefix naming convention is used when you want private functions to do the work and the pattern matching clauses don’t match the API you want for the public interface.
• The do_ functions are declared using defp making them private to the module.
• The public build_text/1 function handles starting the process with all the initial values. It starts the counter at 0 and the initial text with "". This provides the same behavior as the while version. It sets up the state for the loop then calls the private function to do the looping.
• The guard clause when num < total behaves like the condition in the while loop! That guard clause tells us how long we should stay in the loop.
• The final do_ clause matches when we have looped the desired amount and it returns the accumulated text.

Practice Exercises

Now it’s time to put theory into practice! You learn best by doing. The following exercises give you an opportunity to experiment and apply what we are learning here. Take the time to play with it!

Exercise #1 – Compute Order Total

Using recursion, process a list of OrderItem structs to compute an order total. Refer to the following structs for details as needed:

• lib/schemas/order_item.ex
• lib/schemas/item.ex

The order total is computed as an Item’s price * the quantity being ordered. Summing all of those together for the total order price.

The following mix test command will run the tests for the describe block without needing to know the line number. Review the tests to see the data samples being tested.

mix test test/recursion_test.exs --only describe:"order_total/1"

HINT #1: Define defp functions with a do_ prefix to handle the iterating.

HINT #2: This exercise is more like the for loop examples above.

  def order_total(order_items) do
    do_order_total(order_items, 0)
  end

  defp do_order_total([%OrderItem{} = order_item | rest], total) do
    do_order_total(rest, (order_item.quantity * order_item.item.price) + total)
  end

  defp do_order_total([], total) do
    total
  end

Exercise #2 – Counting Active

Using recursion, process a list of Customer structs to count the number of active customers. A Customer has an active boolean flag. Conditionally increment the counter only when a Customer is active. Refer to the following as needed:

• lib/schemas/customer.ex – Defines the customer struct
• test/recursion_test.exs – Shows data examples your code needs to process

The following mix test command will run the tests for the describe block without needing to know the line number.

mix test test/recursion_test.exs --only describe:"count_active/1"

HINT #1: Define defp functions with a do_ prefix to handle the iterating.

HINT #2: This exercise is more like the for loop examples above.

  alias CodeFlow.Schemas.Customer

  def count_active(customers) do
    do_count_active(customers, 0)
  end

  # Active customer, increment counter and recurse
  defp do_count_active([%Customer{active: true} | rest], acc) do
    do_count_active(rest, acc + 1)
  end

  # Not active, don't increment counter, continue recursing
  defp do_count_active([_customer | rest], acc) do
    do_count_active(rest, acc)
  end

  # Reached end of list, return total count
  defp do_count_active([], acc) do
    acc
  end

Exercise #3 – Creating Customers

The goal is to create a desired number of new customer entries. Use the function CodeFlow.Fake.Customers.create/1 to perform the customer create operation. In order to create a valid customer, you must at least provide a name. Something like this could easily exist in a testing framework setup.

Don’t get too hung up on checking that the customer was correctly created, that’s not the focus here. The focus is on loop control.

mix test test/recursion_test.exs --only describe:"create_customers/1"

HINT: This exercise is focused more on re-implementing the while loop we looked at.

  def create_customers(number) do
    do_create_customers(number, 0)
  end

  defp do_create_customers(total, num) when num < total do
    # for simplicity, not handling a failed create
    {:ok, _customer} = Customers.create(%{name: "Customer #{num}"})
    do_create_customers(total, num + 1)
  end

  defp do_create_customers(total, _num) do
    "Created #{total} customers!"
  end

Extra Credit Exercise – Fibonacci Sequence

This one is just for fun! This is only about writing a recursive function. In Computer Science and even job interviews, people want to see that you know how to use recursion. If you aren’t familiar with a Fibonacci Sequence, it is a number sequence where a number is computed by adding the two previous numbers in the sequence together. The only initial given numbers are the first two numbers of the sequence which are 0 and 1.

Confusing? Let’s see an example.

0, 1, 1, 2, 3, 5, 8, 13, ...

The 6th index in the sequence is 8 (using a zero based index). It is computed by adding the previous two numbers 3 and 5 together. Executing your implemented function Recursion.fibonacci(6) should return the value 8.

The test checks that your solution correctly solves for a number of different indexes. Remember: pattern matching is your friend!

mix test test/recursion_test.exs:80

  def fibonacci(0), do: 0
  def fibonacci(1), do: 1

  def fibonacci(index) do
    fibonacci(index - 2) + fibonacci(index - 1)
  end

$ iex -S mix

CodeFlow.Recursion.fibonacci(43)
#=> 433494437

Recap

Do you see the pattern here? The recursive versions have all the same parts as the imperative Javascript versions, just organized differently. The new organization does the following for us:

• removes all variable mutations
• uses recursion for looping
• pattern matching 2 or more function clauses controls the loop
• accumulators are passed through the functions

Additionally, we covered the defp do_perform_some_work naming convention. This naming convention puts a do_ prefix on private functions that do the looping work you need while keeping your module’s public API clean and consistent.