Reversing list with recursion in Elixir

Question

My task is to take a list and then reverse it recursively, using one parameter. What I have arrived at is this solution:

def reverse(l) do
      [head | tail] = l
      cond do

          tail == [] ->
             head

          true ->
             [reverse(tail) , head]

      end 
end

I have attempted having a | instead of a comma in the true statement, but to no avail. The problem with this solution is that it prints out the following when inputting [1,2,3,4,5]:

[[[[5, 4], 3], 2], 1]

It doesn't actually add the head part to the list aside from when returning the final value of the list. (in this case 5)

Answer 1

One cannot expect implicit flattening for [list, elem] as you do in [reverse(tail), head].

The former is a list, and this is why you receive nested lists back.

One way to approach the problem would be to indeed add lists one to another with reverse(tail) ++ [head]. It’s not efficient though because it would produce new lists on each step and is not tail-recursive.

The proper solution would be to introduce an accumulator to collect the processed items

def reverse(input, acc \\ [])
def reverse([], acc), do: acc
def reverse([head | tail], acc) do
  reverse(tail, [head | acc])
end 

reverse([1, 2, 3])
#⇒ [3, 2, 1]

Answer 2

I personally like to use pattern matching in this way instead of the cond as I feel like it makes it easier to reason about it.

defmodule M do

  def reverse(list) do
    reverse_helper(list, [])
  end

  defp reverse_helper([], reversed) do
    reversed
  end

  defp reverse_helper([h|t], reversed) do
    reverse_helper(t, [h|reversed])
  end
end