Introduction

In this post we are going to look at recursive functions, that is functions that call themselves in a loop. We will start with a naive implementation and then make it more efficient using an accumulator. As a special treat, I will show you a way of writing FizzBuzz using this technique.

Setting Up

All of the code in this post can be run using FSI. I recommend using VSCode with the ionide plugin.

Solving The Problem

We are going to start with a naive implementation of the factorial function (!):

To create a recursive function, we use the 'rec' keyword and we would create a function like this:

You'll notice that we have two case, 1 and greater than 1. When n is 1, we return 1 and end the recursion but if it is greater than 1, we return the number multiplied by the factorial of the number - 1 and continue the recursion. If we were to write out what happens, it would look like this:

This is a problem because you can't unwind the calculations until you've calculated all of the iterations but you also need to store all of the parts as well. This means that the larger n gets, the more memory you need to perform the calculation and it can also lead to stack overflows. We can solve this problem with Tail Call Optimisation.

Tail Call Optimisation

The approach we are going to take is to use an accumulator. The first thing that we need to do is to re-write our factorial function:

We leave the public interface of the function intact and create a function enclosed in the outer one to do the recursion. We also need to add a line to start the recursion. You'll notice that we've added an additional parameter which is the accumulator. As we are multiplying, this need to be 1 in this case. Lets write out what happens when we run this function as we did the previous version:

This is much simpler than the previous example, requires very little memory and is extremely efficient.

We can also solve factorial using the reduce and fold functions from the List module.

Now that we've learnt about tail call optimisation using an accumulator, let's look at a harder example, the Fibonacci Sequence.

Expanding The Accumulator

The Fibonacci Sequence is a simple list of numbers where each value is the sum of the previous two:

Let's start with the naive example to calculate the nth item in the sequence:

If you want to see just how inefficient this is, try running fib 50L. It will take almost a minute on a fast machine! Let's have a go at writing a more efficient version that uses tail call optimisation:

Let's write out what happens (ignoring the type):

The 5th item in the sequence is indeed 3 as the list starts at index 0. Try running fibL 50L - It should return almost instantaneously.

We'll now continue on our journey to find as many functional ways of solving FizzBuzz as possible. :)

FizzBuzz Using Recursion

We start with a list of rules that we are going to recurse over:

We then write our fizzbuzz function using tail call optimisation. In this case the accumulator will use string concatenation.

Finally we run the function and print the result:

This is quite a nice extensible approach to the FizzBuzz problem as adding 7-Bazz is as easy as adding another rule.

Other Uses Of Recursion

The examples we've used are necessarily simple to concentrate on tail call optimisation using an accumulator but what would we really use recursion for in a real application? Recursion is great for handling hierarchical data like the file system or XML, converting between flat data and hierarchies and for event loops or loops where there is no defined finish.

Further Reading

As always, Scott Wlaschin's excellent site has many posts on the topic (https://fsharpforfunandprofit.com/posts/recursive-types-and-folds-3b/#series-toc).

Conclusion

In this post we have had a look at recursion in F#. In particular, we have looked at how to use accumulators with tail call optimisation to make recursion more efficient.

This may be the last post in this series. Either way, look out for a new series on creating websites and APIs in F# with Giraffe - Coming soon!

If you have any comments on this series of posts or suggestions for new ones, send me a tweet (@ijrussell) and let me know.