Recursive Functions

Understand how functional programming languages like OCaml rely entirely on recursion for repeated computations.

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)={    0,for n=0n+sum(n1),for n>0 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.

Get hands-on with 1200+ tech skills courses.