这是尾递归吗？

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

这里的无体函数子句只是将[]建立为默认累加器.因为我们总是在前面,为了保持秩序,我们必须在完成后撤销列表.这是非常常见的事情,Enum.reverse在VM中进行了高度优化.