Recursion as a problem solving idiom
The concept of recursion at first seems strange, but once we get past that strangeness feeling, it starts to show off its elegance. This is especially the case with functional languages like OCaml, where it is a preferred way to solve problems instead of loops. Let's see some examples.
gcd(a,b) = a if b = 0 otherwise gcd(b, a mod b)
let rec gcd a b = if b = 0 then a else gcd b (a mod b)
Note that how the actual code naturally follows the algorithm definition.
utop # gcd 18 4;; - : int = 2
A canonical example of recursion.
fact(n) = 1 if n = 0 otherwise n * fact(n-1)
let rec fact n = if n = 0 then 1 else n * fact (n-1)
utop # fact 5;; - : int = 120
Lists and Recursion
Most problems using lists lend nicely to recursion and pattern matching:
Sum of elements
let rec sumn l = match l with  -> 0 | h::t -> h + sumn t
utop # sumn [1;2;3;4;5];; - : int = 15
Return odd indexed elements of a list
let rec odd_elements l = match l with  ->  | fst::  -> [fst] | fst :: snd :: rst -> fst :: odd_elements rst
utop # odd_elements ['a'; 'b'; 'c'; 'd'];; - : char list = [a; c]
Append two lists
let rec appendlist l1 l2 = match l1 with  -> l2 | h::t -> h :: appendlist t l2
utop # appendlist [1;2] [3;4;5];; - : int list = [1; 2; 3; 4; 5]
As we can see that if a problem is (or can be) defined in terms of its own definition but with an input that is smaller than the starting input size, recursion is a neat idiom and functional languages make writing the code in this idiom more natural.