CODEWITHSUNDEEP
f#tail-recursion
piaste
piaste

Reputation: 2058

Why isn't this function tail recursive?

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:

enter image description here

Upvotes: 2

Views: 106

Answers (1)

Random Dev
Random Dev

Reputation: 52270

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

Upvotes: 2

Related Questions