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

这是否已经优化了尾调用？或者每个子句都必须在最后调用自己("偶数"函数的第二个版本不是)？如果没有,如何重构为尾调用递归？

我知道这可以通过过滤器或减少来完成,但我想尝试没有它.

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文档建议在这种情况下将两个结果中的任何一个写入更干净的代码中.

根据神话,使用尾递归函数,反向构建一个列表,然后调用,lists:reverse/1比以正确顺序构建列表的body-recursive函数更快; 原因是body-recursive函数比tail-recursive函数使用更多的内存.

在R12B之前,这在某种程度上是正确的.在R7B之前更是如此.今天,不是那么多.身体递归函数通常使用与尾递归函数相同的内存量.通常不可能预测尾递归或身体递归版本是否会更快.因此,请使用使代码更清晰的版本(提示:它通常是正文递归版本).

有关尾部和体递归的更全面讨论,请参阅Erlang的尾部递归不是银弹.

神话:尾递归函数比递归函数快得多.