recursion - Elixir :为什么尾递归比体递归函数使用更多的内存？

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)

在我的电脑中，尾递归版本的beam.smp 将使用2.5G ~ 3G 内存，而body-recursive 仅使用1G 左右。我是不是误会了什么？

Answer 1

TL;DR: erlang虚拟机似乎将两者都优化为 TCO。

如今，编译器和虚拟机太聪明了，无法预测它们的行为。 tail recursion的优势|不是内存消耗少，而是:

This is to ensure that no system resources, for example, call stack, are consumed.

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

▶ 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'ed。