Recursive Functions

Where are the for/while loops?

Assume you want to calculate the sum, 1 + 2 + 3 + ... + n, for a given n natural number. In a non-functional programming language, we typically use a for or while loop:

int sum (int n) {
   int s = 0;
   for (int i = 1; i <= n; i++) {
      s = s + i;
   }
   return s;
}

This way of programming is inherently imperative because we explicitly specify the steps required to update s via variable assignment within a loop.

In the functional paradigm, however, we express sum as an expression. In particular, we can have a mathematical definition of sum as follows:

$sum(n) = \begin{cases} \;\;\,0, & \text{for } n = 0 \\ n + sum(n-1), & \text{for } n > 0 \end{cases}$

We can translate this definition directly into a recursive function—a function that calls itself. Such a function is marked with the rec keyword in OCaml.