Tail Recursion in C# and F#

For those of you who are unfamiliar with the notion of tail recursion, let me quote Wikipedia’s definition.

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail call, is a recursive call

Tail recursion is essential in functional languages like F#, where iterative solutions are often implemented using recursion. If the recursion gets too deep, a stack overflow occurs, and your program crashes brutally. The rationale behind tail recursion is that if the recursive call is the last operation of the function, the stack frame of the current function invocation can be discarded before the recursive function invocation is made.

Rather than spending too much time discussing programming theory, let me present two equivalent programs, both containing tail recursion.

C#

class Program
{
	static int n = 1000000;

	static void Countdown()
	{
		if (0 > n--) return;
		Countdown();
	}

	static void Main(string[] args)
	{
		Countdown();
		Console.WriteLine("Done");
	}
}

F#

let n = 1000000

let rec countdown n =
    match n with
    | 0 -> ()
    | _ -> countdown (n-1)

countdown n
printfn "Done"

These two programs are semantically equivalent. They both use tail recursion to count from 1 000 000 to zero, before writing “Done” to the console.

Let us first look at the F# solution. Apart from being precise and easy to comprehend, it actually works. In fact, the F# compiler is smart enough to optimize the countdown function into a simple while loop, producing MSIL equivalent to the following C# code:

public static void countdown(int n)
{
    while (true)
    {
        switch (n)
        {
            case 0:
                return;
        }
        n--;
    }
}

But what about the tail recursive C# solution? While tail recursion optimization has been proposed to Microsoft, the current C# compiler does nothing of the kind. Hence, the resulting MSIL contains a recursive Countdown method. The question is then: “Will the C# solution result in a stack overflow?” Interestingly, the answer is: “It depends.”

It turns out, if you compile the C# code with “Platform target: Any CPU” and run it on a 64-bit version of the Microsoft .NET runtime, the JIT compiler will actually perform tail recursion optimization from the MSIL itself, resulting in a working program. If, however, you compile with “Platform target: x86” or run the program on a 32-bit version of the Microsoft .NET runtime, a stack overflow occurs. This behavior is described in the blog post “Tail call JIT conditions” by David Broman. Basically, the feature sets of the 64-bit and 32-bit versions of the JIT compiler do not coincide.

So, unless you are 100 % certain that your C# application will run on the 64-bit runtime, do no employ tail recursion with the intent of preventing stack overflows. Then again, if you are writing imperative C# code, tail recursion will probably not cross your mind as the best solution to any of your problems.

Fibonacci Fun with F#

As you probably know, the Fibonacci sequence is the infinite sequence of integers where each element is the sum of the previous two (the first two elements being 0 and 1). Recently, I was inspired by a blog post, Ruby vs. Haskell – project Euler #25 deathmatch. In particular, I enjoyed the Haskell solution for its simplicity and declarativeness.

I decided to try and solve the same problem, but using F#, the functional programming language being introduced as a first class .NET citizen for the first time with Visual Studio 2010. If you have never seen F# code before, the snippets included in this post may be difficult to comprehend, especially if you are used to reading code written in imperative languages like C# or Java.

To declaratively create infinite sequences in F#, the Seq module provides the unfold function. This function takes two parameters, a generator function and an initial state. The generator function must take a state parameter and produce an option tuple with a sequence element and a new state. In F# notation, the unfold function has the signature Seq.unfold : ('State -> 'T * 'State option) -> 'State -> seq<'T>. Note that if the generator function always returns Some(_) and never None, the resulting sequence will be infinite.

An example of Seq.unfold in action is shown in the following one-liner, producing an infinite sequence of all positive integers.

let positiveIntegers = Seq.unfold (fun x -> Some(x, x + 1)) 1

In this example, the generator function takes an integer state as input. The sequence element produced by this function is the current state, while the next state is calculated by incrementing the current state. Thus, each time the generator function is called, the input integer state is one higher than the previous time. The initial state, 1, is passed as the final parameter to Seq.unfold. The result is the sequence “1, 2, 3, …, ∞” (or, strictly speaking, as far as 32 bit integers go).

So, how do we go from this sequence to the Fibonacci sequence? First of all, since each element of the Fibonacci sequence is the sum of the previous two, the state cannot consist only of a single integer. Rather, the state has to be a tuple of two integers. By choosing (0, 1) as the initial state, the generator function can use the first tuple element as sequence output and construct the next state as ([next], [current] + [next]), where [current] and [next] are the first and second element, respectively, from the current state tuple.

Translated into F# code, this yields the following definition of the Fibonacci sequence.

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (0, 1)

When enumerating this sequence, however, one problem becomes apparent. Element number 48 is a negative number. This is definitely erroneous behavior, as the Fibonacci sequence consists solely of positive integers. The error is due to the limited value space of 32 bit integers, causing an overflow. To circumvent this problem, we can use the BigInteger type, capable of representing integers of arbitrary size. The only change we need to make to our original Fibonacci definition is to change the initial state tuple to contain BigInteger values. The F# type inference system handles the rest.

open System.Numerics

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (BigInteger 0, BigInteger 1)

Now to the actual solution to Project Euler #25. Modelled after the previously mentioned Haskell solution, my solution also counts the number of elements in the Fibonacci sequence having a value less than 10999.

Again, translating this into F# results in the following code.

open System.Numerics

let limit = BigInteger.Pow(BigInteger 10, 999)

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (BigInteger 0, BigInteger 1)

let term =
    fibonacci
    |> Seq.takeWhile (fun n -> n < limit)
    |> Seq.length

printfn "%d" term

I am intrigued by how this functional solution focuses on what the Fibonacci sequence is, rather than how it is calculated. Constructing an infinite Fibonacci sequence in C# would typically require an iterator consisting of an infinite loop, representing state with two local variables. Counting elements having a value less than 10999, however, could easily have been accomplished in a functional manner using LINQ.