You must explicitly state that a function is recursive:
let rec fun ...
This is an implementation of the factorial function recursively in OCaml:
(* requires: [n >= 0] *)
let rec fact n =
if n = 0 then 1
else n * fact (n - 1)
val fact : int -> int = <fun>
The reason that we need to write fact (n - 1) rather than fact n - 1 is because otherwise OCaml will parse the argument as n, rather than n - 1
fact 10;;
- : int = 3628800
What happens if we don't use the rec keyword? OCaml will throw an error.
(* requires [n >= 1] *)
let fib n =
if n = 0 or n = 1 then 1 else fib (n - 1) + fib (n - 2);;
File "[3]", line 3, characters 10-12:
3 | if n = 0 or n = 1 then 1 else fib (n - 1) + fib (n - 2);;
^^
Alert deprecated: Stdlib.or
Use (||) instead.
File "[3]", line 3, characters 31-34:
3 | if n = 0 or n = 1 then 1 else fib (n - 1) + fib (n - 2);;
^^^
Error: Unbound value fib
Hint: If this is a recursive definition,
you should add the 'rec' keyword on line 2
We can fix this by adding the rec keyword.
(* requires [n >= 1] *)
let rec fib n =
if n = 0 || n = 1 then 1 else fib (n - 1) + fib (n - 2);;
val fib : int -> int = <fun>
fib 5;;
- : int = 8