它是一个尾递归

Question

我有下面的代码片段：

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

我在FP世界很新，想知道这是否是一个尾递归？

Answer 1

这不是尾递归。为了运行最后一个表达式（++，列表级联），必须保留[h]，并且新调用flatten(t)将产生一个新的堆栈帧，并且不能替换前一个，因为引用了[h]。

换句话说，通过tail-call-optimization，顶层的函数调用将取代先前的堆栈。该函数调用中的任何表达式都会事先发生，并会在调用时增加堆栈。

尾调优化（包括尾递归）的大多数枚举都使用累加器。要充分利用@ 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在虚拟机中进行了高度优化。