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

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

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

▶ NTC.inf                                                                    
[1]    351729 killed     iex

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

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

旁注：

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

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

elixir: why tail-recursive use more memory than a body-recursive function?

recursion

elixir