Elixir tail-call recursive function

Question

I have this function that finds the even numbers in a list and returns a new list with only those numbers:

  def even([]), do: []

  def even([head | tail]) when rem(head, 2) == 0 do
    [head | even(tail)]
  end

  def even([_head| tail]) do
    even(tail)
  end

Is this already tail-call optimized? Or does every clause have to call itself at the end (the second version of the "even" function doesn't)? If not, how can it be refactored to be tail-call recursive?

I know this can be done with filter or reduce but I wanted to try without it.

user_320615 · Answer

You're right that this function is not tail recursive because the second clause's last call is the list prepend operation, not a call to itself. To make this tail-recursive, you'll have to use an accumulator. Since the accumulation happens in reverse, in the first clause you'll need to reverse the list.

def even(list), do: even(list, [])

def even([], acc), do: :lists.reverse(acc)

def even([head | tail], acc) when rem(head, 2) == 0 do
  even(tail, [head | acc])
end

def even([_head| tail], acc) do
  even(tail, acc)
end

But in Erlang, your "body-recursive" code is automatically optimized and may not be slower than a tail-recursive solution which does a :lists.reverse call at the end. The Erlang documentation recommends writing whichever of the two results in cleaner code in such cases.

According to the myth, using a tail-recursive function that builds a list in reverse followed by a call to lists:reverse/1 is faster than a body-recursive function that builds the list in correct order; the reason being that body-recursive functions use more memory than tail-recursive functions.

That was true to some extent before R12B. It was even more true before R7B. Today, not so much. A body-recursive function generally uses the same amount of memory as a tail-recursive function. It is generally not possible to predict whether the tail-recursive or the body-recursive version will be faster. Therefore, use the version that makes your code cleaner (hint: it is usually the body-recursive version).

For a more thorough discussion about tail and body recursion, see Erlang's Tail Recursion is Not a Silver Bullet.

Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions.

Elixir tail-call recursive function

1 Answers