trjhtr

Below is my code for building the collatz sequence so a given number. I'm trying to make the function tail recursive and I believe that this impelemtation is tail recursive but I'm not yet so comfortable with F# that I can convince myself 100%.

let collatzSeq n =
 let collatz m =
 match m%2 with
 | 0 -> m/2
 | _ -> 3*m + 1
 let rec loop (l,acc) =
 match l with
 | 1 -> acc
 | _ -> let l' = (collatz l) in loop (l',l'::acc)
 loop (n,[n]) |> List.rev

[<EntryPoint>]
let main argv = 
 let col12 = collatzSeq 12
 printfn "%A %d" col12 col12.Length
 0 // return an integer exit code

My concern is does the let .. in loop construct stop this being tail recursive and if it does how do I improve the code to make it tail recursive?

By building two implementaions of a much simpler function you can see that the function in the question is in a form that is tail recursive.

let rec recList n =
 match n with 
 | 1 -> [1]
 | _ -> n :: recList (n - 1)

let accList n =
 let rec loop (l,acc) =
 match l with
 |1 -> acc
 |_ -> let l' = l - 1 in loop(l',l::acc)
 loop (n,) |> List.rev

[<EntryPoint>]
let main argv = 

 // Fails with a stack overflow!
 // printfn "%A" (recList 100000)
 printfn "%A" (accList 10000000)

The recList implementaion again demonstrates that a simple recursive function will cause the stack to explode, on my machine this happened between 10000 and 100000.

The accList version which mirrors the function in the question works with values much larger than the one that caused the recList function to fail.