Is the following function tail recursive?

Question

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.

Easiest way to answer these sort of questions: feed in a gigantic list which you think will trigger the pathological behaviour and see what happens. — John Palmer
I would rather compile it and then look at resulting code with ILSpy. More reliable. Also note that the result may differ depending on whether optimizations are enabled. — Fyodor Soikin
Well, it handled lists of cardinality 1,00,000,000 (one hundred million) without batting an eyelid, so I'll just assume that my question can be answered in the affirmative. — Shredderroy

Tomas Petricek Tomas Petricek · Accepted Answer · 2016-07-01T07:42:02

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

Is the following function tail recursive?

2 Answers