在 Elixir 中使用递归反转列表

Question

我的任务是获取一个列表，然后使用一个参数递归地反转它。我得到的是这个解决方案：

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

          tail == [] ->
             head

          true ->
             [reverse(tail) , head]

      end 
end

我试过一个 |而不是 true 语句中的逗号，但无济于事。这个解决方案的问题是它在输入 [1,2,3,4,5] 时打印出以下内容：

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

除了返回列表的最终值外，它实际上并没有添加头部部分到列表中。（在本例中为 5）

Answer 1

不能像在 [reverse(tail), head].

中那样对 [list, elem] 进行隐式扁平化

前者是一个列表，这就是您收到嵌套列表的原因。

解决该问题的一种方法是使用 reverse(tail) ++ [head] 将一个列表添加到另一个列表。虽然它效率不高，因为它会在每个步骤中生成新列表并且不是尾递归的。

正确的解决方案是引入一个累加器来收集处理过的项目

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

我个人喜欢以这种方式使用模式匹配而不是 cond，因为我觉得这样更容易推理它。

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

Answer 3

要修复您的解决方案，您可以使用 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 例如需要 [1, [2]] 和 returns [1, 2]。但这种解决方案效率不高。您可以使用@aleksei-matiushkin 解决方案，也可以使用尾递归的 foldl：

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

在 Elixir 中使用递归反转列表

Reversing list with recursion in Elixir

recursion

list

elixir