下面的函数是尾递归的吗？

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: !
at FSI_0002.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at .$FSI_0003.main@() Stopped due to error

但是如果您将代码更改为非尾递归 - 例如通过修改最后一行首先进行递归调用 (helper t1 t2) && (h1 = h2)，然后堆栈跟踪显示所有递归调用：

System.Exception: ! at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 4
at FSI_0004.helper[A](FSharpList'1 currLst1, FSharpList'1 currLst2) in test.fsx:line 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

下面的函数是尾递归的吗？

Is the following function tail recursive?

recursion

f#

tail-recursion