Elixir 尾调用递归函数

Question

我有这个函数可以找到列表中的偶数和 returns 一个只有这些数字的新列表：

  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 中，您的“正文递归”代码会自动优化，并且可能不会比在末尾执行 :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.

Elixir 尾调用递归函数

Elixir tail-call recursive function

recursion

elixir

tail-call-optimization