这个函数使用尾递归吗？

Question

我想知道oCaml是否会将此代码优化为尾递归，如果是的话，F#是否也会这样做？

let rec sum xs =
  match xs with
    | [] -> 0
    | x :: xs' -> x + sum xs'

- user34537

Answer 1

在递归情况下（即xs不为空的情况下），最后一个被评估的操作是加法。为了使函数成为尾递归，最后一个被评估的操作需要是对sum的递归调用。

这样的函数通常使用带有累加器的辅助函数来定义，以使它们成为尾递归。在这种情况下，它将是一个函数，该函数接受要求和的列表和当前总和的值。如果列表为空，则返回当前总和的值。如果列表不为空，则使用列表的尾部和列表的头部之和作为参数调用自身。然后，sum函数将简单地使用列表和0作为当前总和的值来调用辅助函数。

- sepp2k

---

是的，所以对于 oCaml 来说优化并不难。只需添加一个 currentVal 参数并调用 sum xs'，currentSum。知道这么简单，我想知道它是否进行了优化。所以你说它没有优化，嗯...我在这台机器上没有 oCaml bins，所以我无法检查并知道它是否进行了优化。 - user34537

在这种情况下，使用它可能会进行优化，但是如果您依赖它，那么在稍微更复杂的情况下，编译器无法进行转换时，您将遇到堆栈溢出的问题。例如，您可以期望从另一个模块中获得纯函数的相同转换，并且您期望这样做，但由于分离编译和接口未指定哪些函数为纯函数，因此编译器无法进行转换。 - Pascal Cuoq

Answer 2

不，这段代码不是尾递归的，ocaml也不会自动转换。你需要自己去做。

我不确定F#是否会进行优化。

- Rémi