|
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 (n-2) 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 non-tail 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/ocaml-faq/) 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
|