CODEWITHSUNDEEP
ocamltail-recursion
user34537
user34537

Reputation:

Does this function use tail recursion?

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'

Upvotes: 9

Views: 1025

Answers (2)

sepp2k
sepp2k

Reputation: 370435

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.

Upvotes: 13

Rémi
Rémi

Reputation: 8342

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.

Upvotes: 5

Related Questions