CODEWITHSUNDEEP
recursionf#tail-recursion
Shredderroy
Shredderroy

Reputation: 2920

Is the following function tail recursive?

I have a function in which the starred line is a conjunction involving a recursive call. As conjunctions work, if h1 <> h2 then the recursive call will not be made. But if the call is made, then will the compiler still backtrack and perform a whole bunch of conjunctions over true values? Or will it elide this unnecessary step?

In other words, is the following function effectively tail recursive?

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

Yes, I know that the starred line should be written if h1 = h2 then helper t1 t2 else false. But I am just curious.

Thanks in advance.

Upvotes: 7

Views: 171

Answers (2)

s952163
s952163

Reputation: 6324

From ILSpy it would appear so:

    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

Upvotes: 6

Tomas Petricek
Tomas Petricek

Reputation: 243041

Another easy trick to find out whether the function is tail-recursive is to throw an exception and look at the stack trace. For example, you can modify helper as follows:

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)

If you now call helper [1..10] [1..10], you get a stack trace that looks like this:

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

But if you change the code to be non-tail-recursive - e.g. by modifying the last line to make the recursive call first (helper t1 t2) && (h1 = h2), then the stack trace shows all the recursive calls:

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@()

Upvotes: 7

Related Questions