Tail-Recursive Lucas Sequence Computation in OCaml Example

In OCaml, implement a function lucas : int -> int such that lucas n is the $n$-th Lucas number. On 64-bit platforms, only $\{L_0,L_1,\dots ,L_{88}\}$ can be represented as values of type int.

Solution

Disregarding the input domain check, a naive implementation of the lucas function would be as follows:

let rec lucas : int -> int =
  function
  | 0 -> 2
  | 1 -> 1
  | n -> lucas (n - 1) + lucas (n - 2)

In terms of runtime complexity, this implementation is inefficient since there are duplicate calls to lucas occurring in the computation of lucas (n - 1) + lucas (n - 2). Space complexity isn't better either since those calls to lucas in lucas (n - 1) + lucas (n - 2) are not tail calls, which means that new stack frames are allocated whenever the recursion depth increases.

To address both issues, we can generalize the problem of finding $L_n$ to the problem of finding $L_n$ when we're given $L_{n-1}$ and $L_{n-2}$. We define a tail-recursive helper function lucas_helper : int -> int -> int -> int such that lucas_helper n a b is $L_n$ when a is $L_{n-1}$, and b is $L_{n-2}$. These extra parameters a and b act as a memoization mechanism for the latest two Lucas numbers computed.

let lucas : int -> int =
  let rec lucas_helper : int -> int -> int -> int =
    fun n a b ->
      if n = 0 then
        a
      else
        lucas_helper (n - 1) b (a + b)
  in
  fun n ->
    if n < 0 || n > 88 then
      raise (Invalid_argument "lucas")
    else
      lucas_helper n 2 1

Alternatively, without using recursion, we would iterate from 0 to n - 1 and successively compute $L_0,L_1,\dots ,L_n$ using mutable references.

let lucas : int -> int =
  fun n ->
    if n < 0 || n > 88 then
      raise (Invalid_argument "lucas")
    else
      let i : int ref = ref 0
      and a : int ref = ref 2
      and b : int ref = ref 1
      in
      while !i < n do
        let next : int = !a + !b in
        a := !b;
        b := next;
        i := !i + 1
      done;
      !a