我如何知道函数是否在F＃中进行尾递归？

2018-06-28 20:23:23

我写了follwing函数：

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

我如何知道F＃编译器是否将它变成了一个循环？有没有办法找到没有使用反射器（我没有反射器的经验，我不知道C＃）？

编辑：另外，是否有可能编写一个尾递归函数而不使用内部函数，或者是否需要循环驻留？

另外，F＃std lib中是否有一个函数多次运行给定的函数，每次都将它的最后一个输出作为输入？比方说，我有一个字符串，我想在字符串上运行一个函数，然后在结果字符串上再次运行它，等等......

不幸的是，没有微不足道的方法。

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

当然，你可以在大量的测试数据上试试你的功能，看看它是否爆炸。

F＃编译器将为所有尾调用生成尾尾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

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

链接地址: http://www.djcxy.com/p/80563.html

上一篇: How do I know if a function is tail recursive in F#

下一篇: What's happening?