Elixir无限递归会导致栈溢出吗？

Question

Elixir无限递归会导致栈溢出吗？

stack-overflowelixir

21

Elixir编程中有很多种不同的教程，其中一些认为存储状态或运行无限循环可以通过将数据转移到代理或任务中，或者通过需要状态的函数实现无限递归来进行。它们没有提及递归的深度限制或任何其他注意事项。

由于搜索“Elixir堆栈溢出”只会得到这个网站的搜索结果，让我们消除歧义并在这里问：Elixir中有哪些实现保证可以确保以无限递归作为“循环”的方法不会导致堆栈溢出，特别是当状态信息一路上被传递时？

- bright-star

9

从你提供的第二个链接中可以得知：在 Elixir/Erlang 中，这种递归不会导致堆栈溢出，因为这两种语言对所谓的“尾调用”有特殊处理，在字节码级别上，将被转换为跳转/转到指令。因此，该代码仅仅运行一个无限循环。 - Hristo Iliev

1

谢谢。我会澄清我的措辞，以保持这个问题的实用性。 - bright-star

5

请注意，这并非适用于所有递归，只适用于尾递归。尾递归意味着在递归调用后不会执行当前层级的任何代码（即递归发生在函数尾部），因此无需保留当前层级的堆栈空间，可以安全地重用于嵌套调用。也不需要进行函数调用——跳转到函数体开头就足够了。这也是F#和其他语言中如何优化尾递归的方式。 - Hristo Iliev

2

有关保证，请参见此处（尾调用优化部分）和此处（尾递归的长度部分）。 - Hristo Iliev

1

是的，Hristo所说的一切都是正确的，但你需要确保（就像Sasa在下面指出的那样）你不会无意中编写代码，以防止Erlang应用TCO。 - Onorio Catenacci

请问您能否更新第二个链接？它已经失效了，我在网站上也找不到任何相关的内容。可能已被删除。 - Burak Kaymakci

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sasajuric · Accepted Answer

总结Hristo的精彩评论，这种常规机制叫做“尾调用优化”（TCO），它确保如果一个函数最后执行的是调用另一个函数（或自身），那么不会进行栈推送，而是会发生简单的跳转。

对于何为尾调用存在一些微妙的细微差别。让我们看几个例子。最简单的例子是：

def foo do
  # ...

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

总成本拥有条件表达式也适用:

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

另一个破坏尾调用优化的例子是在 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）。