Introduction to Functional Programming in F# – Part 11

12. Juli

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 (!):

5! = 5 * 4 * 3 * 2 * 1 = 120

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

let rec fact n = // int -> int
    match n with
    | 1 -> 1
    | n -> n * fact (n-1)

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:

fact 5 = 5 * fact 4
       = 5 * (4 * fact 3)
       = 5 * (4 * (3 * fact 2))
       = 5 * (4 * (3 * (2 * fact 1)))
       = 5 * (4 * (3 * (2 * 1)))
       = 5 * (4 * (3 * 2))
       = 5 * (4 * 6)
       = 5 * 24
       = 120

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:

let fact n =
    let rec go n acc =
        match n with
        | 1 -> acc
        | _ -> go (n-1) (acc * n)
    go n 1

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:

fact 5 = go 5 1
       = go 4 5
       = go 3 20
       = go 2 60
       = go 1 120
       = 120

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.

let fact n = // int -> int
    [1..n] |> List.reduce (*)

let fact n = // int -> int
    [1..n] |> List.fold (*) 1

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:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

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

let rec fib (n:int64) =
    match n with
    | 0L -> 0L
    | 1L -> 1L
    | s -> fib (s-1L) + fib (s-2L)

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 fibL (n:int64) =
    let rec go n (a,b) =
        match n with
        | 0L -> a
        | 1L -> b
        | n -> go (n-1L) (b,a+b)
    go n (0L,1L)

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

fibL 5 = go 5 (0,1)
       = go 4 (1,1+0)
       = go 3 (1,1+1)
       = go 2 (2,1+2)
       = go 1 (3,2+3)
       = 3

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:

let fizzRules = 
    [
        (fun i -> if i % 3 = 0 then "Fizz" else "")
        (fun i -> if i % 5 = 0 then "Buzz" else "")
    ]

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

let fizzBuzz rules i =
    let rec loop rl s =
        match rl, s with
        | [], "" -> i.ToString()
        | [], _ -> s
        | h::t, _ -> loop t (s + h i) // h is a function from fizzRules
    loop rules ""

Finally we run the function and print the result:

[ 1 .. 105 ]
|> List.map (fizzBuzz fizzRules)
|> List.iter (printfn "%s")

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.

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.

Introduction to Functional Programming in F#

Ian Russell