Interestingly, mutable data is also sufficient to achieve general recursion in a typed language:

  let fact' = ref (fun x -> x) in
  let fact = fun n -> if n = 0 then 1 else n * !fact' (n-1) in
  fact' := fact; fact 3