If you haven’t read part 1 of this series, I highly recommend you doing so. Otherwise, you might be a bit lost.

Now, back to functional programming. We last left off talking about the basics of functional programming: types, equivalence, expressions, existential equivalence, and referential transparency. Moving forward, we are moving onto a few more advanced topics: recursion and sorting.

Recursion

In functional programming, recursion is one of the core techniques used to write coherent and working code. If you’ve written code in C, Java, or any other imperative languages, you’ll see recursion used rarely. However, in functional programming, recursion is almost a must.

The mathematical idea behind recursion is going through all viable elements in a set that satisfy some property. So, let’s try using a math example to show the power of recursion. We’re going to generate the Fibonacci numbers recursively.


fun fib 0 = 1
| fib 1 = 1
| fib n = fib (n-1) + fib (n-2)


Let’s now dissect this code. In recursive programming, we need to have base cases and a recursive (sometimes called inductive) case. In this case, we have two base cases, n = 0 and n = 1. In the Fibonacci series, we know that the first and second numbers are both 1. So, we use those as our base cases. Now, to calculate a Fibonacci number, we add together the two previous Fibonacci numbers. So, our recursive case is a self-call to the fib function. However, we need to follow the formula, so we decrease n by 1 and 2.

This is a very simple example of recursive programming, but almost all recursive programming follows this template: base cases, then recursive self-calls to accumulate until a base case is met.

Sorting

Sorting in functional languages usually requires recursion. To show this, let’s go through a basic sort function: insertion sort. First, we need a comparison function:


fun compare (x: int, y: int) : order =
if x < y then LESS else if x > y then GREATER
else EQUAL


Now, to write the sort function.


fun sort (x : int, nil : int list) : int list = [x]
| sort (x : int, y::L : int list) : int list = case compare (x, y) of
| GREATER => y :: sort (x, L)
| _ => x :: y :: L


This sort function inserts the value into it’s correct position.