Elixir 无限递归是否会溢出堆栈？

Question

A number of different how-tos 在 Elixir 编程中表达了这样一种观点，即存储状态或运行无限循环是通过将数据旋转到 Agent 或 Task 中，或者通过函数的无限递归来惯用地完成的那需要状态。他们没有提及递归的深度限制或任何其他警告。

由于搜索 "Elixir stack overflow" 只会导致对该网站的点击，让我消除歧义并在这里问：Elixir 中有哪些实现保证以确保无限递归作为 [=16 的方法=] 不会导致堆栈溢出，尤其是在沿途携带状态信息时？

Answer 1

为了总结 Hristo 的精彩评论，一般机制称为 "Tail Call Optimization" (TCO)，它确保如果一个函数做的最后一件事是调用另一个函数（或它自己），那么就不会不是堆栈推送。相反，将发生简单的跳转。

关于什么是尾调用有一些细微的差别。让我们看几个例子。最简单的是：

def foo do
  # ...

  bar(...)  # tail call -> nothing is pushed to the stack
end

TCO 也将申请条件表达式：

def foo do
  # ...

  if (...) do
    # ...
    bar(...)            # tail call
  else
    # ...
    baz(...)            # tail call
  end
end

这是可行的，因为函数最后做的事情是调用函数。 if 的结果是 bar 或 baz 的结果，因此无需将任何内容压入堆栈。

相比之下，如果调用函数在调用另一个函数之后做某事，则不是尾调用，不会发生 TCO:

def foo do
  # ...

  # Not a tail call since we're doing something after bar returns
  # (increment the result by 1)
  1 + bar(...)    
end

打破 TCO 的另一个例子是调用 try 中的函数：

def foo do
  try do
    bar(...)    # not a tail call
  rescue
    # ...
  end
end

还值得一提的是，由于 TCO，发生异常时您不会在堆栈跟踪中看到某些函数：

def foo do
  # ...
  bar(...)  # at this point foo "disappears" from stack trace
end

def bar(...) do
  # ...
  raise("error")
end

此错误的堆栈转储将不包括 foo，因为它不再在堆栈中（它实际上被替换为 bar）。

Does Elixir infinite recursion ever overflow the stack?