
utop

Recursive functions must be explicitely written with the keyword `rec`. Here is an example with the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number).

utop # let fib n =
if n < 2 then 1 else
let rec go i prev prevprev =
let res = prev + prevprev in
if i = 0 then
res
else
go (pred i) res prev
in
go (n2) 1 1
;;
val fib : int > int = <fun>
utop # fib 4;;
 : int = 5
utop # fib 5;;
 : int = 8

There's an important concept when writing recursive code: **tail optimization**. It means that the compiler can optimize your code if the recursive function doesn't have to remember some state when it calls itself. Without that, Each call creates a new stack and you end up with stack overflows. This is an example of a nontail optimized recursive function (notice that each call has to remember what `i` is to be able to use the return value of the recursive call.

utop # let rec sum i =
if i = 0 then 0
else
let rest = sum (pred i) in
i + rest
;;
val sum : int > int = <fun>
utop # sum 3;;
 : int = 6
utop # sum 4;;
 : int = 10

Finally, here's an example copied from [Daniil Baturin](https://baturin.org/docs/ocamlfaq/) on how to write functions that recursively call one another.

utop # let rec even x =
match x with
 0 > true
 _ > odd (x  1)
and odd x =
match x with
 0 > false
 _ > even(x  1)
;;
val even : int > bool = <fun>
val odd : int > bool = <fun>
# odd 19 ;;
 : bool = true
# even 42 ;;
 : bool = true
