4
\$\begingroup\$

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?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.