Recursion and Pattern Matching

Recursion

Like most people coming from the land of imperative programming, one of the first things that jumped out at me when exploring functional programming was that idiomatic thinking tended towards recursion rather than iteration. While this was initially a hurdle, I’ve managed to do a 180 degree turn and now find I prefer to reason about recursive functions.

The idea is straight forward: Figure out the base case for your problem and break it down into smaller subsets of the same problem until you reach that base case. Then just solve each of these smaller (simpler) versions of the problem and combine the results to get your final answer (divide and conquer).

Pattern Matching

One of the next things I’ve found quite prevalent, especially in the F# world, was the extensive use of a powerful concept known as pattern matching. I’ve often heard of it as a case/switch statement on steroids, but that doesn’t do it justice. It is true that at its core, pattern matching is used for conditional logic. However, other conditional constructs such as your standard if, else and case statements pale in comparison.

I am going to devote a couple of blog posts on pattern matching in my two favourite programming languages: F# and Elixir. These posts will cover more advanced pattern matching topics such as guard clauses, matching algebraic datatypes, active patterns, binary pattern matching and more. I hope that they will open your eyes to the almighty and powerful concept.

For this blog post, I thought it would be a good idea to ease into pattern matching by looking at the following:

• Basic pattern matching
• A simple (perhaps contrived), yet canonical recursive example function (factorial)
• Looking at the slightly different idiomatic approaches between F# and Elixir

Now onto the problem definition.

Factorial Definition

The problem we’ll be solving is called the factorial. Wikipedia sums it up nicely:

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,
5! = 5 x 4 x 3 x 2 x 1=120
The value of 0! is 1, according to the convention for an empty product.

For our sample functions I want to keep things simple. This means we’ll be ignoring issues such as dealing with negative integers or bad input parameters etc. Although it would be worth revisiting the factorial solution in the more advanced posts when we investigate guard clauses. I will ensure that the functions are tail recursive though.

Solving Factorial Using Recursion and Pattern Matching with F#

F# is a statically-typed, multi-paradigm (with an emphasis on functional-first), cross-platform programming language built on top of the .Net/Mono runtimes.

Here is a fairly idiomatic and straightforward solution for solving the factorial of an integer using F#:

Let’s enter this in F# interactive. We are returned the following type signature:

val factorial : n:int -> int

If you are not an F# programmer, this just means we have a function that takes an integer (called n) and returns a new integer. We essentially transform the integer from one to another, based on the logic inside of factorial. I should also mention that the compiler can infer the type information based on the code inside the function. It will make it as generic as possible and you can use explicit type annotations to override and/or help the compiler out when required.

Now we’ll break this function down and see what it is doing.

In F#, it is fairly common to define an outer function that contains an internal function used for recursion. Our outer function is factorial and our internal function is factorial' (pronounced factorial prime, due to the tick mark at the end). You can call the inner function whatever you like, but in my experience this naming convention seems to be popular. Note the rec keyword in the factorial' definition. This is a requirement by the F# compiler to allow a function to call itself.

Looking further at factorial', we see that it takes an integer, n (note: even though it has the same name as the outer function’s n parameter, it is a different value) and an accumulator, acc. The accumulator is threaded through the function to keep a running total on our calculation to ensure we have no deferred operations through each recursive call. This is called tail recursion and allows the function to work similar to an iterative loop (I believe the F# compiler even creates a loop in the generated IL code). In other words, it prevents the chance of a stack overflow.

Moving into the factorial' implementation, we finally see our use of pattern matching (albeit, in this simple case an if/else clause would suffice). We are matching the value of n against two possible values (again ignoring negative numbers and guard clauses to keep things simple for this post):

• The base case, 0
  • If the value of n is 0, we have hit the base case and can simply return our total via the accumulator.
• For all other cases (denoted in F# as _)
  • We take the current value of n and subtract 1 (moving us towards the based case)
  • We take the current value of n and multiply it by our current total to get our new total (the accumulator)
  • Both of these values are passed into a recursive call to factorial'

A quick note about pattern matching in F#: The compiler will complain if your match statement does not cover all possible (for the most part) inputs. In our case, we were only interested in the base case vs. any other case, so we can use the _ catch-all (like a default case in a switch statement). The usefulness of this is more evident when doing more complicated pattern matching against things such as algebraic datatypes.

The last thing to discuss is the line factorial' n 1. This is the last call in the outer factorial function that takes the n value initially requested and passes it in to the factorial' inner function, along with a starting accumulator value. We pass the value 1 because that is the legal value for a factorial of 0 (in case the base case of factorial 0 is called to the outer function).

Next, we’ll try the function out. Instead of just doing a single value, let’s have some fun with F# language features. We’re going to take a list of integers from 0 to 10 and pipe that list into the F# standard List.map function. This will apply the factorial function to each integer in the list and return a new list of the transformed values.

[0..10] |> List.map factorial

This returns the following result:

val it : int list = [1; 1; 2; 6; 24; 120; 720; 5040; 40320; 362880; 3628800]

Checking this new list against the solution table (top right side of this Wikipedia page), it appears our function works as expected.

Solving Factorial Using Recursion and Pattern Matching with Elixir

Elixir is a dynamically-typed, functional and concurrent programming language built on top of the Erlang virtual machine (BEAM).

Here is my attempt at an idiomatic solution for solving the factorial of an integer using Elixir:

At first glance, you’ll notice that the implementation appears to be quite different from the F# code. This is actually what prompted me to write this blog post. Elixir seems to take pattern matching even further than F#. I am still exploring the abilities of both languages, so I may be incorrect. Regardless, this solution shows a different approach to recursion and pattern matching that is quite interesting.

Let’s analyze this solution.

In Elixir, you’ll notice that we can have multiple functions with the same name and even the same number of input parameters (and basically the same types, although remember that Elixir is dynamically typed). This is possible because Elixir can pattern match against the parameters you pass in to a function and it will call the correct version. Think of it as method overloading in your favourite object oriented language. However, Elixir can actually match against the value of a parameter!

The first factorial function definition is the equivalent to the outer function from the F# solution. We call it with an integer, which then begins the recursion by calling another version of the factorial function with the value of n and an initialized accumulator with a value of 1 (similar to the last line in the F# solution’s outer function).

The second factorial function is our base case. When we have an n value of 0, we simply return the accumulator. This is equivalent to the match n with | 0 -> acc pattern in the F# solution.

The third function is our equivalent to the all other cases match clause from the F# solution: | _ -> factorial' (n - 1) (acc * n). In essence, we are moving towards our base case by subtracting 1 from the current value of n. That result is passed along to the next recursive call to factorial along with our accumulator expression, which is the current total multiplied by n. Once n reaches the value 0, we hit our second function, the base case.

Like F#, the Elixir compiler will complain if you miss a case in your pattern matching. It will also let you know if the functions are in the incorrect order, which may cause one of the functions to become unreachable code (the F# compiler also does this in match expressions). Lastly, the compiler will warn you when you don’t group the functions together properly. If I was to move the base case function to the top of the function definitions (which seems natural), I will get the following warning:

clauses for the same def should be grouped together, def factorial/2 was previously defined

This is interesting. Elixir is actually considering the two functions that have the same arity (number of parameters) to be part of the same definition, which requires them to be grouped together. In a way, it seems like the Elixir compiler takes these two functions and turns them into something like the F# match statement under the covers. I’d like to investigate the semantics further, but that is how I reason about it.

Let’s try the function out. We’ll do the equivalent to the F# test: Take a list of integers from 0 to 10 and pipe that list into the Elixir Enum.map function. This will apply the factorial function to each integer in the list and return a new list of the transformed values. For my test I used the interactive Elixir shell IEx.

0..10 |> Enum.map(&(MyMath.factorial(&1)))

And the result is the same as the F# solution:

[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

Summary

While F# and Elixir take different approaches, the solutions presented are more similar than they first appear. Regardless of the implementations details, what is important is that recursion and pattern matching can be combined to create some powerful solutions. While our example was rather simple, it still illustrates the concept and its usefulness.

I hope I have piqued your curiosity to explore both pattern matching and recursion futher. I will continue to dig deeper into pattern matching and some of the more advanced applications updating my blog with my findings.