recursion - Elixir尾调用递归函数

Question

我有此函数，用于查找列表中的偶数并返回仅包含这些数字的新列表:

  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

这个已经优化了吗？还是每个子句都必须在末尾调用自身(“even”函数的第二个版本不需要)？如果不是，如何将其重构为尾调用递归？

我知道可以使用filter或reduce来完成此操作，但我想尝试不使用它。

Answer 1

没错，该函数不是尾部递归的，因为第二个子句的最后一个调用是列表前缀操作，而不是对自身的调用。要使此尾递归，必须使用一个累加器。由于累积是反向进行的，因此在第一个子句中，您需要将列表反向。

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

但是在Erlang中，您的“body-recursive”代码会自动优化，并且可能不会比尾部递归解决方案慢，后者在最后会进行 :lists.reverse调用。在这种情况下，Erlang文档建议使用干净的代码编写两个结果中的任何一个。

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.