14. Elixir: Recursion

15 Sept 20244 min read

Prev Next

Here’s the recurse.ex file we ended up with in the video.

defmodule Recurse do
  def loopy([head | tail]) do
    IO.puts "Head: #{head} Tail: #{inspect(tail)}"
    loopy(tail)
  end
end
 
Recurse.loopy([1, 2, 3, 4, 5])

Recursion in Elixir

Exercise: Sum The Numbers

Here’s the recurse.ex file we ended up with in the video:

defmodule Recurse do
  def loopy([head | tail]) do
    IO.puts "Head: #{head} Tail: #{inspect(tail)}"
    loopy(tail)
  end
 
  def loopy([]), do: IO.puts "Done!"
end
 
Recurse.loopy([1, 2, 3, 4, 5])

Now that you know how to keep a bit of state each time through a recursive “loop”, rename loopy to sum and have it sum the numbers in the list. For example, given the numbers 1 to 5, the termination clause should return 15.

Solution:

defmodule Recurse do
  def sum([head | tail], total) do
    IO.puts "Total: #{total} Head: #{head} Tail: #{inspect(tail)}"
    sum(tail, total + head)
  end
 
  def sum([], total), do: total
end
 
IO.puts Recurse.sum([1, 2, 3, 4, 5], 0)

Exercise: Triple All The Numbers

Write a triple function that takes a list of numbers and returns a new list consisting of each of the original numbers multiplied by 3. For example:

IO.inspect Recurse.triple([1, 2, 3, 4, 5])

The result should be:

[3, 6, 9, 12, 15]

The key is to remember that you can make a list using the [head | tail] syntax. For example, the literal [1 | [2 | [3 | []]]] makes the list [1, 2, 3]. So… each time triple is called with [head | tail], make a new list where the head is the original head multiplied by 3 and the tail is the result of recursively calling triple with the original tail. When triple is called with [] (the terminal clause), return an empty list. In other words, you’ll end up recursively creating the list as a series of heads and tails [3 | [6 | [9 | [12 | [15 | []]]]]] which evaluates to [3, 6, 9, 12, 15].

Solution:

defmodule Recurse do
  def triple([head | tail]) do
    [head * 3 | triple(tail)]
  end
 
  def triple([]), do: []
end
 
IO.inspect Recurse.triple([1, 2, 3, 4, 5])

Tail-Call Optimization

In the video, we mentioned that Elixir performs tail-call optimization to keep the memory footprint of recursion to a minimum. We took advantage of this when implementing the parse_headers function:

def parse_headers([head | tail], headers) do
  ...
  parse_headers(tail, headers)
end
 
def parse_headers([], headers), do: headers

Because the last thing the parse_headers function does is call itself (a tail call), Elixir performs tail-call optimization. Calling the parse_headers function recursively this way doesn’t push any new frames onto the call stack, and so no additional memory is consumed.

You can implement the triple function to take advantage of tail-call optimization using an accumulator. Here’s the tail-recursive version of triple:

Tail-Recursive Triple Function:

defmodule Recurse do
  def triple(list) do
    triple(list, [])
  end
 
  defp triple([head | tail], current_list) do
    triple(tail, [head * 3 | current_list])
  end
 
  defp triple([], current_list) do
    current_list |> Enum.reverse()
  end
end
 
IO.inspect Recurse.triple([1, 2, 3, 4, 5])
`
 
Heres how it works:
 
 
  * The `triple/1` function calls the private `triple/2` function with the list of numbers and an accumulator `current_list` that starts as an empty list `[]`.
  * The first `triple/2` function head matches a non-empty list of numbers and calls itself (a tail call) with the lists tail and a new list where the head is the original head multiplied by 3 and the tail is the current accumulator list.
  * Finally, the second `triple/2` function head matches an empty list and returns the list of accumulated numbers reversed, because each tripled number was added to the head of the accumulator list.
 
 
Thus, the accumulator list was populated in reversed order, so it needs to be reversed. Its common to reverse the result of a tail-recursive function that builds up a list in this way.
 
 
### Code So Far
 
The code for this section is in the **recursion** directory found within the **video-code** directory of the
<a href="https://drive.google.com/uc?export=download&id=118mbTTbsXqhFmk__PV1lYmtByQp9m167" download="download">code bundle</a>
 
[Prev](./13-matching-heads-and-tails.md)
[Next](./15-slicing-dicing-enums.md)

Graph View

Backlinks