recursion - 以下函数尾部递归吗？

我有一个函数，其中加星号的行是涉及递归调用的连词。作为连词起作用，如果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。但是我很好奇。

提前致谢。

最佳答案

找出函数是否为尾递归的另一个简单技巧是引发异常并查看堆栈跟踪。例如，您可以按以下方式修改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 ：！
在test.fsx：line 4中的FSI_0002.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）处
在。$ FSI_0003.main @（）
由于错误而停止


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


System.Exception ：！
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在test.fsx：第4行中的FSI_0004.helper [A]（FSharpList'1 currLst1，FSharpList'1 currLst2）
在。$ FSI_0005.main @（）