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# std lib 中是否有一个函数可以多次运行给定函数，每次都将最后的输出作为输入？假设我有一个字符串，我想在该字符串上运行一个函数，然后在结果字符串上再次运行它，依此类推...

Answer 1

不幸的是，没有简单的方法。

阅读源代码并使用类型并通过检查确定某件事是否是尾调用（是“最后一件事”，而不是在“try”块中）并不难，但人们会事后猜测自己并犯错误。没有简单的自动化方法（除了检查生成的代码之外）。

当然，你可以在一大块测试数据上尝试一下你的函数，看看它是否会爆炸。

F# 编译器将为所有尾调用生成 .tail IL 指令（除非使用编译器标志来关闭它们 - 用于当您想要保留堆栈帧进行调试时），但直接尾递归函数将是例外优化为循环。 （编辑：我认为现在 F# 编译器在可以证明此调用站点没有递归循环的情况下也无法发出 .tail；这是一种优化，因为 .tail 操作码在许多平台上稍慢一些。）

'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

Answer 2

我喜欢 Paul Graham 在 On Lisp 中制定的经验法则：如果还有 工作要做 ，例如操纵递归调用输出，则该调用不是尾递归。

Answer 3

2023 更新

从 F# 8 开始，编译器现在可以为您检查这一点！用

TailCallAttribute

标记该函数，如果您提供非尾递归的实现，您将收到警告。

例如这段代码：

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

发出两个

Warning FS3569 : The member or function 'fibNaive' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.

实例（每个递归调用一个）

虽然此代码不会发出警告：

[<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

为了获得奖励积分，最好将

<WarningsAsErrors>FS3569</WarningsAsErrors>

添加到您的 fsproj 中，将其转变为错误。