以下函数尾递归吗？

Question

我有一个函数,其中星号行是一个涉及递归调用的连接.当连词工作时,如果h1 <> h2那时将不进行递归调用.但是如果进行了调用,那么编译器是否仍会回溯并在true值上执行一大堆连接？还是会忽视这个不必要的步骤？

换句话说,以下函数是否有效尾递归？

let isExtensionOf<'A when 'A : equality> (lst1 : list<'A>) (lst2 : list<'A>) : bool =
    let rec helper (currLst1 : list<'A>) (currLst2 : list<'A>) : bool =
        match currLst1, currLst2 with
        | h1 :: _, [] -> false
        | [], _ -> true
        | h1 :: t1, h2 :: t2 -> (h1 = h2) && (helper t1 t2) // *
    helper lst1 lst2

是的,我知道应该写星号if h1 = h2 then helper t1 t2 else false.但我只是好奇.

提前致谢.

Answer 1

找出函数是否是尾递归的另一个简单技巧是抛出异常并查看堆栈跟踪.例如,您可以修改helper如下:

let rec helper (currLst1 : list<'A>) (currLst2 : list<'A>) : bool =
    match currLst1, currLst2 with
    | h1 :: _, [] -> failwith "!"
    | [], _ -> failwith "!"
    | h1 :: t1, h2 :: t2 -> (h1 = h2) && (helper t1 t2)

如果您现在调用helper [1..10] [1..10],则会得到如下所示的堆栈跟踪:

System.Exception :!
在FSI_0002.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)中test.fsx:第4行
at.$ FSI_0003.main @()由于错误而停止

但是如果你将代码更改为非尾递归 - 例如通过修改最后一行来进行递归调用(helper t1 t2) && (h1 = h2),那么堆栈跟踪会显示所有递归调用:

System.Exception :! 在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2):
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)的第4行:第4行
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2):
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)的第4行:第4行
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2):
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)的第4行:第4行
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2):
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)的第4行:第4行
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2):
在test.fsx中的FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)的第4行:第4行
在FSI_0004.helper [A](FSharpList'1 currLst1,FSharpList'1 currLst2)中test.fsx:第4行
at.$ FSI_0005.main @()

Answer 2

从ILSpy看起来如此:

    IL_0000: nop
    IL_0001: newobj instance void class '<StartupCode$ConsoleApplication3>.$Program'/helper@10<!!A>::.ctor()
    IL_0006: stloc.0
    IL_0007: ldloc.0
    IL_0008: ldarg.1
    IL_0009: ldarg.2
    IL_000a: tail.
    IL_000c: call !!0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!A>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!A>>::InvokeFast<bool>(class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!1, !!0>>, !0, !1)
    IL_0011: ret