Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / F#

F# 14: Recursion

Rate me:
Please Sign up or sign in to vote.
5.00/5 (6 votes)
4 Apr 2014CPOL5 min read 21.5K   7   2
Recursion in F#

Introduction

We continue our journey into F#, and this time, we will look at recursion. We have already seen this in a number of places, namely when we talked about Lists and also Pattern Matching. So some of this should be vaguely familiar to you.

Simple Example

Let's start with the most basic example which is typical of what we have seen before. This example simply adds all the elements in an input list.

F#
let rec sumFunction theList =
    match theList with
    | []    -> 0
    | head::tail -> head + sumFunction tail

printfn "sumFunction [1..10] = %A" (sumFunction [1..10])

Which when run produces the following output:

image

There are several take away points from this small code snippet, such as:

  • We had to use the “rec” keyword to make the function a recursive one. Without the use of the “rec” keyword, the compiler would issue an error:

image

  • We put a pattern match in against an empty list.
  • We use the “::” (cons) pattern match, such that we are able to match a head and a tail part of a list

So let's now turn our attention to another example, this time, we will use the well known Factorial example. Here is a standard way to implement this recursively:

F#
let rec factorial n = 
    if n = 0 then 1 else n * factorial (n-1)

This looks fine, let's take it for a spin. Let's try to run it with input:

F#
printfn "factorial System.Int32.MaxValue = %A" (factorial 10)

Which when run does indeed work just fine, and gives us the following results:

image

F#
printfn "factorial System.Int32.MaxValue = %A" (factorial System.Int32.MaxValue)

So what happens now? Let’s see…

We now get this output, which is um not so great, in fact, this is as my old boss would have said a “Cluster f***” (pardon my French)

image

So why did this happen? What did we do wrong?

Well, if we turn our attention to the actual Visual Studio IDE and look at the “CallStack” window, we can see some pointers as to why this may be happening.

image

So we got a whole bunch of calls placed on the stack. The reason for this is actually due to how the code is structured. Let’s examine the code again:

F#
let rec factorial n = 
    if n = 0 then 1 else n * factorial (n-1)

It can be seen that we use n, but we are also waiting for the result of the recursive call to “factorial” to give us a result, such that we can multiply them together. All of these calls need to be placed somewhere, and they end up being placed on the stack, and eventually we run out of space and get a StackOverFlowException thrown (quite rightly so).

What you should be asking yourself is, is there a better way I could have written my code to avoid this?

Well yes, there is, it is called “Tail Recursion”, which also uses a technique called the “Accumulator Pattern”.

Tail Recursion

What does the “Accumulator Pattern” actually mean. For all intents and purposes, it really means that we pass an extra value into the function, which is an accumulation value that you can use with each iterative call. This simple change means we no longer need to push things on to the stack to keep the temporary value, obviously the stack is still involved with the recursion itself, but we do not have to push unnecessary values to the stack, As a result, the compiler is able to optimize the code.

Ok, let's see the new / better code (for the sake of me not having to wait too long to see a result, I have gone for a small value of “5”, but rest assured, you would not get a StackOverFlowException thrown if you use this technique, for larger numbers.

F#
let factorialProducingForLoop x =
    // Keep track of both x and an accumulator value (acc)
    let rec tailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            tailRecursiveFactorial (x - 1) (acc * x)
    tailRecursiveFactorial x 1

printfn "factorialProducingForLoop 5 = %A" (factorialProducingForLoop 5)

It can be seen that I have used a non recursive function that is called, that function called contains a nested function which does the recursion, and is called with an initial accumulator value and the original function input value.

Here is the proof that this works fine:

image

To fully understand the different between the non tail recursive version and the better tail recursive version, let’s have a look at the decompiled source of them (I am using DotPeek to decompile the code, but use what you will).

Non Tail Recursive Version

Here is the decompiled C# code for the non optimized non tail recursive version, where it can clearly be seen that this will heavily involve the stack, which is evident in the Invoke() method shown below, where it can be seen that the Invoke() method is called time and time again.

F#
[Serializable]
  internal class factorial\u004015 : FSharpFunc<int, int>
  {
    internal factorial\u004015()
    {
    }

    public override int Invoke(int n)
    {
      if (n == 0)
        return 1;
      else
        return n * this.Invoke(n - 1);
    }
  }

Tail Recursive Version

Here is the decompiled C# code for the optimized tail recursive version, where we can see that this has been converted into a simple for loop which is ALL contained in a single call to the Invoke() method. Which puts us in a much better/happier place.

F#
[Serializable]
  internal class tailRecursiveFactorial\u004021 : OptimizedClosures.FSharpFunc<int, int, int>
  {
    internal tailRecursiveFactorial\u004021()
    {
    }

    public override int Invoke(int x, int acc)
    {
      for (; x > 1; {
        int num;
        x = num;
      }
      )
      {
        num = x - 1;
        acc *= x;
      }
      return acc;
    }
  }

  [Serializable]
  internal class factorialProducingForLoop\u004020 : FSharpFunc<int, int>
  {
    internal factorialProducingForLoop\u004020()
    {
    }

    public override int Invoke(int x)
    {
      return FSharpFunc<int, int>.InvokeFast<int>(
            (FSharpFunc<int, FSharpFunc<int, int>>) 
                    new Program.tailRecursiveFactorial\u004021(), x, 1);
    }

I just wanted to mention one more thing, if you took this already cool (and totally fit for purpose) tail recursive code:

F#
let factorialProducingForLoop x =
    // Keep track of both x and an accumulator value (acc)
    let rec tailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            tailRecursiveFactorial (x - 1) (acc * x)
    tailRecursiveFactorial x 1

Which gave us these results:

image

But instead decided you prefer to write it like this where we DO NOT create an inner recursive function, but rather choose to have 2 separate functions, and we alter the order of the value and the accumulator:

F#
let rec tailRecursiveFactorial acc x =
    if x <= 1 then 
        acc
    else 
        tailRecursiveFactorial  (acc * x) (x - 1)

let factorialProducingWhileLoop data = tailRecursiveFactorial 1 data
    
printfn "factorialProducingWhileLoop 5 = %A" (factorialProducingWhileLoop 5)

image

It can be seen we get the same results, but let's examine the decompiled code:

F#
[Serializable]
  internal class tailRecursiveFactorial\u004032 : OptimizedClosures.FSharpFunc<int, int, int>
  {
    internal tailRecursiveFactorial\u004032()
    {
    }

    public override int Invoke(int acc, int x)
    {
      while (x > 1)
      {
        int num = acc * x;
        --x;
        acc = num;
      }
      return acc;
    }
  }

  [Serializable]
  internal class factorialProducingWhileLoop\u004037 : FSharpFunc<int, int>
  {
    public FSharpFunc<int, FSharpFunc<int, int>> tailRecursiveFactorial;

    internal factorialProducingWhileLoop\u004037
              (FSharpFunc<int, FSharpFunc<int, int>> tailRecursiveFactorial)
    {
      this.tailRecursiveFactorial = tailRecursiveFactorial;
    }

    public override int Invoke(int data)
    {
      return FSharpFunc<int, int>.InvokeFast<int>(this.tailRecursiveFactorial, 1, data);
    }
  }

It can be seen that this time, we get a while loop in the Invoke() method call.

I don’t know if this adds any value to the post, but I just wanted to see what would happen if I swapped the order and had no nested function, and instead went for 2 functions instead of one function that had an inner function.

I guess I am just a geek (and proud of it).

Callbacks

There is another way to deal with recursion which uses a callback based technique, but to be honest, I have found it not to be that easy to understand, and a little hairy for right here, right now. If you are interested, I am sure a quick Google around will get you what you want.

So in the end, this post was quite a short one for a fairly complex subject, but there is not much more I wanted to say.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United Kingdom United Kingdom
I currently hold the following qualifications (amongst others, I also studied Music Technology and Electronics, for my sins)

- MSc (Passed with distinctions), in Information Technology for E-Commerce
- BSc Hons (1st class) in Computer Science & Artificial Intelligence

Both of these at Sussex University UK.

Award(s)

I am lucky enough to have won a few awards for Zany Crazy code articles over the years

  • Microsoft C# MVP 2016
  • Codeproject MVP 2016
  • Microsoft C# MVP 2015
  • Codeproject MVP 2015
  • Microsoft C# MVP 2014
  • Codeproject MVP 2014
  • Microsoft C# MVP 2013
  • Codeproject MVP 2013
  • Microsoft C# MVP 2012
  • Codeproject MVP 2012
  • Microsoft C# MVP 2011
  • Codeproject MVP 2011
  • Microsoft C# MVP 2010
  • Codeproject MVP 2010
  • Microsoft C# MVP 2009
  • Codeproject MVP 2009
  • Microsoft C# MVP 2008
  • Codeproject MVP 2008
  • And numerous codeproject awards which you can see over at my blog

Comments and Discussions

 
QuestionMy 5 Pin
phil.o13-Jun-14 6:12
professionalphil.o13-Jun-14 6:12 
Thank you Sacha, very instructive on so many levels, as often Smile | :)
There are two kinds of people in the world: those who separate humankind in two distinct categories, and those who don't.

"I have two hobbies: breasts." DSK

AnswerRe: My 5 Pin
Sacha Barber13-Jun-14 6:26
Sacha Barber13-Jun-14 6:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.