长生不老药：为什么尾递归比体递归函数使用更多的内存？

Question

我现在正在阅读Learn Functional Programming with Elixir，在第 4 章中，作者谈到了尾调用优化，即尾递归函数将使用比体递归函数更少的内存。但是当我尝试了书中的例子时，结果却相反。

# tail-recursive
defmodule TRFactorial do
  def of(n), do: factorial_of(n, 1)
  defp factorial_of(0, acc), do: acc
  defp factorial_of(n, acc) when n > 0, do: factorial_of(n - 1, n * acc)
end

TRFactorial.of(200_000)


# body-recursive 
defmodule Factorial do
  def of(0), do: 1
  def of(n) when n > 0, do: n * of(n - 1)
end

Factorial.of(200_000)

在我的电脑中，tail-recursive版本的beam.smp会使用2.5G~3G内存，而body-recursive只使用1G左右。我误解了什么吗？

Answer 1

TL;DR： erlang虚拟机似乎都优化了 TCO。

现在编译器和虚拟机太聪明了，无法预测它们的行为。尾递归的好处不是内存消耗少，而是：

这是为了确保不消耗系统资源，例如调用堆栈。

当调用不是尾递归时，必须在调用之间保留堆栈。考虑以下示例。

? defmodule NTC do
    def inf do
      inf()
      IO.puts(".")
      DateTime.utc_now()
    end
  end

这里我们需要保留堆栈，以便在递归返回时继续执行调用者。不会，因为这个递归是无限的。编译器无法优化它，这是我们得到的：

? NTC.inf                                                                    
[1]    351729 killed     iex

请注意，没有发生任何输出，这意味着我们一直在递归调用自己，直到堆栈爆炸。使用 TCO，无限递归是可能的（并且它广泛用于消息处理。）

回到你的例子。正如我们所看到的，TCO 在两种情况下都产生了（否则我们最终会出现堆栈溢出），前者在专用变量中保留一个累加器，而后者仅使用堆栈上的返回值。您会看到这个收益：elixir是不可变的，并且每次调用都会复制变量内容（对于 200K 的阶乘来说是巨大的）并保存在内存中。

边注：

您可以使用:erts_debug.df(Factorial)（这会Elixir.Factorial.dis在同一目录中生成文件）反汇编两个模块，并看到调用是隐式的 TCO。