Int64 usage in recursive functions-CodePudding

I have the following code written in Ocaml to try and generate the first 50 catalan numbers:

let rec f n:int64=
 if n<1 then 1L
 else (4*n-2)*f((n-1L))/(n 1L)
;;
for i = 0 to 50 do
  Printf.printf "%d\n"(f i)
done;

But the problem is that the recursion function doesn't seem to accept Int64 values and seems to want Int instead despite me notating n as int64:

File "/proc/self/fd/0", line 3, characters 19-21:
3 |  else (4*n-2)*f((n-1L))/(n 1L)
                       ^^
Error: This expression has type int64 but an expression was expected of type
         int
exit status 2

Is there a way to ensure I can int64 numbers here with recursion?

CodePudding user response：

Your problem isn't recursion per se, it's that the operators in OCaml are strongly typed. So the - operator is of type int -> int -> int.

Without getting into lots of fussing with the syntax, the easiest fix is probably to use the named functions of the Int64 module. You can use Int64.sub rather than -, for example.

You can use the notation Int64.(... <expr> ...) to avoid repeating the module name. If you rewrite your code this way, you get something like this:

let rec f (n : int64) : int64 =
    Int64.(
        if n < 1L then 1L
        else
            mul (sub (mul 4L n) 2L)
                (f (div (sub n 1L) (add n 1L)))
    )

Looking at the results computed by this function, they don't look like Catalan numbers to me. In fact the 50th Catalan number is too large to be represented as an int64 value. So there is still some work to do. But this is how to get past the problem you're seeing (IMHO).

If you really want to work with such large numbers, you probably want to look at the Zarith module.