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)

Aleksei Matiushkin · Accepted Answer · 2022-01-20 10:46:00Z

8

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]

answered Jan 20, 2022 at 10:46

Aleksei Matiushkin

121k12 gold badges109 silver badges173 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

prnvbn · Accepted Answer · 2022-01-21 01:47:45Z

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

edited Jan 21, 2022 at 1:47

answered Jan 20, 2022 at 10:46

prnvbn

1,0913 gold badges11 silver badges31 bronze badges

Comments

S4eed3sm · Accepted Answer · 2022-01-20 14:28:25Z

0

For fixing your solution you could use List.flatten:

  @spec reverse(list()) :: list()
  def reverse([]), do: []

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

      true ->
        List.flatten(reverse(tail) ++ head)
    end
  end

Flatten for example takes [1, [2]] and returns [1, 2]. But this solution is not efficient. You could use @aleksei-matiushkin solutions or you can use foldl which is tail recursive:

  @spec reverse_fold(list()) :: list()
  def reverse_fold(l) do
    List.foldl(l, [], fn x, acc ->
      [x | acc]
    end)
  end

answered Jan 20, 2022 at 14:28

S4eed3sm

1,4788 silver badges23 bronze badges

Collectives™ on Stack Overflow

Reversing list with recursion in Elixir

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related