Why isn't this function tail recursive?

Question

I wrote a basic Eratosthenes's sieve function, that originally ended in head::(innerSieve tail), which I noticed wasn't recursive.

Then I modified it as follows to use an accumulator. This code should be tail recursive now:

let Sieve n =     

    let rec innerSieve primes numbers =     
        match numbers with
        | [] -> primes
        | h :: t -> innerSieve (h :: primes) (List.filter (fun x -> x % h > 0) t) 

    innerSieve [] [2 .. n] |> List.rev

printf "%A" (Sieve 10000)

However, even in release mode, the memory usage of this function keeps growing extremely fast with the size of n (+1-2MB per every +1000). Am I missing something?

EDIT: Screenshot of VS running it with n = 100M:

Why do you think the memory usage is related to tail calls? Have you used a profiler? — Luaan
Yes (see addition to question for screenshot). With n = 100M, the memory usage quickly surpasses 2GB and hits an OutOfMemoryException shortly thereafter. The snapshot feature can't terminate, but it detects millions of objects. With TCO, there should be at most a single list of numbers in memory, if I understand it correctly? — piaste
well 100.000.000 Int32 values will be ~380MB alone (just from your [2..n]) - now add all the intermediate lists you are generating ... seems to add up ... — Random Dev
no - it just means that you don't allocate stuff for your function-calls on the stack — Random Dev

Random Dev Random Dev · Accepted Answer · 2015-08-19T11:34:14

To your question: the function is tail recursive - this does not mean that it's magically memory-effective though.

Your real problem is the way Lists are handled/kept in memory (those get very big, very fast.

That's the problem with lists: they are not really optimal if they get big (to much overhead...) so the usual first step is to go arrays instead.

And yeah it works fine (memroy-wise) here:

let inline divides d n = n % d > 0

let rec innerSieve primes numbers =     
    if Array.isEmpty numbers
    then primes
    else 
        let h = numbers.[0]
        let numbers' = numbers |> Array.filter (divides h)
        in innerSieve (h :: primes) numbers'

let Sieve n =     
    innerSieve [] [| 2 .. n |] |> List.rev

of course this too will run a long time ... but on my machine the memory consumption is <200MB so not to bad IMO (...of course my machine is still thinking and will so for some while so probably I just kill the process again and call it a day - you can let it run instead ;) ).

BTW: it might be a fun excercise to switch this to seq instead of list so you can see the primes pop up one after another ... might make the wait time more pleasant

Why isn't this function tail recursive?

1 Answers