有没有一种方法可以明确地编写一个elixir函数以进行尾递归优化？

Question

在Clojure中，例如，您可以使用recur特殊形式来明确使用非堆栈消耗递归调用的意图，并由编译器验证。正如在Clojure docs中所写的那样：

"除尾位置以外的recur是错误的", "recur是功能性的，在尾部位置上的使用由编译器验证"

在Elixir中，您可以将函数定义为一系列子句，并在它们之间进行递归调用。是否有一种确定定义的函数将进行尾调用优化的方法？

- sanrodari

---

简单的答案是在Erlang和Elixir中，函数调用是尾递归优化的，除非你编写的代码阻止了它。基本上，如果你对函数的返回值进行任何操作，例如将1添加到返回值中，那么它就不是尾递归优化的，因为必须维护一个堆栈。 - Onorio Catenacci

Answer 1

编译器不会优化 函数 本身，而是优化对该函数的调用。这可以是函数内部对自身的调用，也可以是对其他函数的调用，这并不重要。

在Clojure中情况并非如此，recur 只能返回到最新的“递归点”（无论是 loop 还是 fn），这使得没有“外部帮助”，例如 trampoline，互递归将不可能。这更像是一种临时解决方案，但问题太大了，需要一个恰当的解决方案需要太多。

在Elixir中确保其被优化的方法很简单：它需要成为实际的尾调用。仅此而已。

在计算机科学中，尾调用是作为过程最后一项操作执行的子例程调用。

这可以通过视觉检查代码轻松确定。

如果Clojure按照这种方式工作，则以下两个定义将等效：

(defn x [] (x))     ; <- StackOverflowError if called
(defn x [] (recur)) ; <- hangs if called

但如果您想要强制执行这一点并在失败时中止，您必须进行以下操作之一：

• 编译前，例如使用某些标记进行静态代码分析以获得“所需的TCO”
• 部署前，例如使用将触发堆栈溢出的测试

后者似乎更实用，特别是对于纯函数。

我没有找到任何现有的解决方案来实现这一点。

- D-side

---

你能确认一下尾调用必须只是一个函数调用而没有其他内容吗？也就是说，如果最后一条语句是 funt(n)，那么这就是一个尾调用；但如果是 1 + funct(n)，那么它将无法进行尾调用优化。 - DavidC

@DavidC 如果返回值有任何计算（例如将返回值加1），则必须创建一个新的堆栈帧，并且调用无法进行尾递归优化。 - Onorio Catenacci