Does this function use tail recursion?

Question

I am wondering if oCaml optimizes this code to be tail recursive and if so does F#?

let rec sum xs =
  match xs with
    | [] -> 0
    | x :: xs' -> x + sum xs'

Answer 1

In the recursive case (i.e. the case that xs is not empty) the last evaluated operation is the addition. For the function to be tail-recursive the last evaluated operation needs to be the recursive call to sum.

Functions like this are usually defined using a helper function with an accumulator to make them tail-recursive. In this case that would be a function that takes the list to be summed and the current value of the sum. If the list is empty, it would return the current value of the sum. If the list is not empty, it would call itself with the tail of the list and the current value of the sum + the head of the list as arguments. The sum function would then simply call the helper function with the list and 0 as the current value of the sum.

Answer 2

No, this code is not tail recursive, and ocaml won't transform it. You have to do it yourself.

I don't know for F#, but I doubt it will optimize this.