elixir - 是尾递归吗

Question

我有以下代码片段:

def flatten([h|t]), do: [h] ++ flatten(t)

我在 fp 世界中很新，想知道这是否是尾递归？

Answer 1

那不是尾递归。为了运行最后一个表达式( ++ ，列表连接)， [h]必须保持周围和新的电话 flatten(t)将产生一个新的堆栈帧，并且不能因为对 [h] 的引用而仅仅替换前一个堆栈帧。 .

换句话说，通过尾调用优化，顶层的函数调用将替换之前的堆栈。该函数调用中的任何表达式都是事先发生的，并且在调用它们时会增加堆栈。

大多数尾调用优化(包括尾递归)的枚举都使用累加器。为了利用@GavinBrelstaff 的代码，这是尾递归形式:

defmodule RC do
  def flatten(list, acc \\ [])
  def flatten([], acc), do: Enum.reverse(acc)
  def flatten([h|t], acc) when is_list(h), do: flatten(h++t, acc)
  def flatten([h|t], acc), do: flatten(t, [h|acc])
end

这里的 bodyless 函数子句只是将 [] 建立为默认累加器。因为我们总是在前置，为了保持顺序，我们必须在完成后反转列表。这是很常见的事情，并且 Enum.reverse 在 VM 中进行了高度优化。