如何判断在F#中一个函数是否是尾递归的

Question

我写了下面这个函数:

let str2lst str =
    let rec f s acc =
      match s with
        | "" -> acc
        | _  -> f (s.Substring 1) (s.[0]::acc)
    f str []

如何知道F#编译器是否将其转换为循环？有没有办法在不使用Reflector（我对Reflector没有经验，也不懂C#）的情况下找出？

编辑：另外，有没有可能编写一个尾递归函数而不使用内部函数，或者必须在循环中使用内部函数？

此外，在F#标准库中是否有一个函数可以运行给定的函数多次，每次都将上一次的输出作为输入？比方说，我有一个字符串，想要在字符串上运行一个函数，然后再次在结果字符串上运行该函数，以此类推...

- Dave Berk

---

请参见https://dev59.com/flbUa4cB1Zd3GeqPAaFf。 - Brian

Answer 1

很遗憾，没有简单的方法。 阅读源代码并使用类型来确定某个东西是否为尾调用并不太难，只需检查它是否是“最后一件事”，而且不在“try”块中即可，但人们往往会自我怀疑并犯错。没有简单的自动化方式（除了例如检查生成的代码）。 当然，您可以将函数应用于大量测试数据并查看是否出现问题。 F＃编译器将为所有尾调用生成.tail IL指令（除非使用编译器标志来关闭它们-用于在调试时保留堆栈帧的情况），唯一的例外是直接尾递归函数将被优化为循环。（编辑：我认为现在F＃编译器还会在可以证明通过此调用站点不存在递归循环的情况下不发出.tail；鉴于在许多平台上.tai​​l操作码速度较慢，这是一种优化。） 'tailcall'是一个保留关键字，想法是未来的F＃版本可能允许您编写例如：

tailcall func args

如果不是尾递归调用，则会收到警告/错误。只有那些自然不是尾递归的函数（因此需要额外的累加器参数）才会使您进入“内部函数”惯用语。

这是您所要求的代码示例：

let rec nTimes n f x =
    if n = 0 then
        x
    else
        nTimes (n-1) f (f x)

let r = nTimes 3 (fun s -> s ^ " is a rose") "A rose"
printfn "%s" r

- Brian

---

“tailcall”很有趣，因为它让你指定调用的位置，而不是更有用的整个函数的“tailrec”声明。你能有一个“部分尾递归”函数吗？ - Stephen Swensen

@StephenSwensen 您绝对可以这样做。 控制流程分支可以导致在尾调用和非尾调用之间选择一种替代方案，并且您可能只想在编译时检查实际上是尾调用的那一个。 let rec f x = if x> 0 then f（1+x）else 0 + f（1+x）说明了这个概念，尽管显然它不会终止。 - Barend Venter

Answer 2

我喜欢保罗·格雷厄姆在《On Lisp》中提出的经验法则：如果还有剩余的工作需要完成，例如操纵递归调用输出，则该调用不是尾递归。

- deprecated

Answer 3

编译器可以为您检查这一点，从F# 8开始！使用TailCallAttribute标记函数，如果您提供的实现不是尾递归的，您将收到一个警告。

例如，以下代码：

[<TailCall>]
let rec fibNaive n =
    if n <= 1 then n
    else fibNaive (n - 1) + fibNaive (n - 2)

发出两个实例的警告FS3569：成员或函数'fibNaive'具有'TailCallAttribute'属性，但未以尾递归方式使用。（每个递归调用一个）

而这段代码不会发出任何警告：

[<TailCall>]
let fibFast n =
    let rec fibFast x y n =
        match n with
        | _ when n < 1 -> x
        | 1 -> y
        | _ -> fibFast y (x + y) (n - 1)
    fibFast 0 1 n

为了加分，将这个转化为一个错误可能是个好主意，通过在你的fsproj中添加FS3569来实现。

- Jwosty