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

There are multiple algorithms out there for finding the greatest common divisor. I wrote about one in an earlier post. But euclid's algorithm (over 2 millenia old) is elegant:

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

Factorial

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.