OCaml By Examples

recursion

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
next: hash tables