Why is this not tail recursive

Question

I've got a (co?)recursive pair of functions that process a list of tuples, and fold them into batches based on some start and end criteria.

I don't do f# that much so I may be being stupid.

I've already amended a simple non tail recursive version into this, by explicitly introducing a "tot" parameter that constitutes the current folded state, what I believed to be tail recursive, yet I get the dreaded stack overflow on large inputs....(in both debugger and (debug) .exe)

There probably is a better way of doing this as an explicit fold...but that's almost not the point, the point is why is it seemingly not tail recursice?

    let rec ignoreUntil2 (xs : List<(string * string)>)  tot = //: List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> = 
        match xs with              
        | [] -> tot
        | ((s1,s2)::tail) -> 
            if s2.StartsWith("Start importing record: Product") then
                takeUntil2 [] ((s1,s2)::tail) tot
            else
                ignoreUntil2 tail tot
and takeUntil2 acc xs tot = // : List<(string * string)> -> List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> =
        match xs with
        | [] -> acc :: tot
        | ((s1,s2)::tail)   ->
            let newAcc = ((s1,s2)::acc)
            if s2.StartsWith("Finished importing record: Product") then
                ignoreUntil2 tail (newAcc :: tot)
            else
                takeUntil2 newAcc tail tot

sepp2k sepp2k · Accepted Answer · 2018-05-04T12:20:32

Your code is tail recursive.

(in both debugger and (debug) .exe)

By default the F# compiler does not eliminate tail calls in debug mode. You'll need to either enable the --tailcalls option explicitly or compile in release mode.

Why is this not tail recursive

1 Answers