Is it a tail recursion

Question

I have following code snippet:

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

I pretty new in the fp world and want to know if this is a tail recursion?

Answer 1

That is not tail recursion. In order for the last expression (++, the list concatenation) to be run, [h] must be kept around and the new call to flatten(t) will result in a new stack frame and cannot just replace the previous one because of the reference to [h].

In other words, with tail-call-optimization, the top level's function call will replace the previous stack. Any expressions within that function call happen before hand and will grow the stack when they are invoked.

Most kinds of enumeration that are tail-call optimized (including tail-recursive) make use of an accumulator. To take advantage of @GavinBrelstaff's code, this is the tail recursive form:

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

The bodyless function clause here just establishes [] as a default accumulator. Because we're always prepending, in order to preserve order, we have to reverse the list when we're done. This is very common thing to do, and Enum.reverse is highly optimized in the VM.