Recursion

The classic FP method for handling indefinite loops is to use recursion. In brief, for those of you unfamiliar with it, recursion is the use of a function that calls itself. A condition of some sort determines whether there should be another iteration or whether to actually return data.

If the decision is made at the end of the recursive function, this is known as tail recursion.

A functional and recursive implementation of Snakes and Ladders might look like this:

public record Player
{
    public int Position { get; set; }
    public int Number { get; set; }
}

public record GameState
{
    public IEnumerable<Player> Players { get; set; }
    public int CurrentPlayer { get; set; }
    public int NumberOfPlayers { get; set; }
}

private static Player UpdatePlayer(Player player, int roll)
{
    var afterDieRoll = player with { Position = player.Position + roll };
    var afterSnakeOrLadder = afterDieRoll with
    {
        Position = SnakesAndLadders.ContainsKey(afterDieRoll.Position)
            ? SnakesAndLadders[afterDieRoll.Position]
            : afterDieRoll.Position
    };
    return afterSnakeOrLadder;
}

private static GameState PlaySnakesAndLaddersRecursive(
    GameState state,
    IDieRoll die)
{
    var roll = die.Roll();

    var newState = state with
    {
        CurrentPlayer = roll == 6
            ? state.CurrentPlayer
            : state.CurrentPlayer == state.NumberOfPlayers
                ? 1
                : state.CurrentPlayer + 1,
        Players = state.Players.Select(x =>
                x.Number == state.CurrentPlayer
                    ? UpdatePlayer(x, roll)
                    : x
            ).ToArray()
    };

    return newState.Players.Any(x => x.Position >= 100)
        ? newState
        : PlaySnakesAndLaddersRecursive(newState, die);
}

public int PlaySnakesAndLaddersRecursive(int noPlayers, IDieRoll die)
{
    var state = new GameState
    {
        CurrentPlayer = 1,
        Players = Enumerable.Range(1, noPlayers)
            .Select(x => (x, 1))
            .Select(x => new Player
            {
                Number = x.Item1,
                Position = x.Item2
            }),
        NumberOfPlayers = noPlayers
    };

    var finalState = PlaySnakesAndLaddersRecursive(state, die);
    return finalState.Players.First(x => x.Position >= 100).Number;
}

Job done, right? Well, not really, and I would think very carefully before using a function like this one. The issue is that every nested function call adds a new item onto the stack in the .NET runtime, and if the code has a lot of recursive calls, that can either negatively affect performance or kill the application with a stack overflow exception.

If there are guaranteed to be only a handful of iterations, nothing is fundamentally wrong with the recursive approach. You’d also have to be sure that this is revisited if the code’s usage is ever significantly changed following an enhancement. This rarely used function with a few iterations one day could turn into something heavily used with hundreds of iterations. If that ever happens, the business might wonder why its wonderful application suddenly becomes near unresponsive almost overnight.

So, as I said, think very carefully before using a recursive algorithm in C#. This has the advantage of being relatively simple and not requiring you to write any boilerplate to make it happen.

I’ve seen another possibility discussed online, and that’s to add a post-build event that directly manipulates the .NET IL that C# compiles to so that C# makes retrospective use of the F# tail call optimization feature. That’s clever but sounds too much like hard work to me. It would be a potential extra maintenance task too.

In the next section, I’ll present a technique to simulate tail call optimization in C#.

Trampolining

I’m not entirely sure where the term trampolining came from, but it predates .NET. The earliest references I could find were academic papers from the ’90s, looking at implementing some of the features of LISP in C. I’d guess it’s even a little older than that, though.

The basic idea of trampolining is that we have a function that takes a thunk as a parameter, a thunk being a block of code stored in a variable. In C#, these are implemented as Func or Action. Having got the thunk, we create an indefinite loop with while(true) and some way of assessing a condition that determines whether the loop should terminate. This might be done with an additional Func that returns a bool or some sort of wrapper object that needs to be updated with each iteration by the thunk.

But at the end of the day, what we’re looking at is basically hiding a while loop at the back of our codebase. It’s true that while isn’t purely functional, but this is one of those places where we might need to compromise. Fundamentally, C# is a hybrid language, supporting both OOP and FP paradigms. There are always going to be places where it’s not going to be possible for C# to behave in exactly the way F# does. This is one of them.

We could implement trampolining in numerous ways, but this is the one I’d tend to go for:

public static class FunctionalExtensions
{
    public static T IterateUntil<T>(
        this T @this,
        Func<T, T> updateFunction,
        Func<T, bool> endCondition)
    {
        var currentThis = @this;

        while (!endCondition(currentThis))
        {
            currentThis = updateFunction(currentThis);
        }

        return currentThis;
    }
}

By attaching to type T, which is a generic, this extension method therefore attaches to everything in the C# codebase. The first parameter is a Func delegate that updates the type that T represents to a new form based on whatever rules the outside world defines. The second is another Func that returns the condition that will cause the loop to terminate.

Since this is a simple while loop, there aren’t any issues with the size of the stack. The code is not pure FP, though. It’s a compromise. At the very least, it’s a single instance of a while loop that’s hidden somewhere, deep in the codebase. It may also be that one day Microsoft will release a new feature that enables proper tail call optimization to be implemented somehow, in which case this function can be reimplemented and the code should continue to work as it did, but with one instance fewer of imperative code features:

public int PlaySnakesAndLaddersTrampolining(int noPlayers, IDieRoll die)
{
    var state = new GameState
    {
        CurrentPlayer = 1,
        Players = Enumerable.Range(1, noPlayers)
            .Select(x => (x, 1))
            .Select(x => new Player
            {
                Number = x.Item1,
                Position = x.Item2
            }),
        NumberOfPlayers = noPlayers
    };

    var finalState = state.IterateUntil(x =>
    {
        var roll = die.Roll();

        var newState = state with
        {
            CurrentPlayer = roll == 6
                ? state.CurrentPlayer
                : state.CurrentPlayer == state.NumberOfPlayers
                    ? 1
                    : state.CurrentPlayer + 1,
            Players = state.Players.Select(x =>
                x.Number == state.CurrentPlayer
                    ? UpdatePlayer(x, roll)
                    : x
            ).ToArray()
        };

        return newState;
    }, x => x.Players.Any(y => y.Position >= 100));

    return finalState.Players.First(x => x.Position >= 100).Number;
}

There is another way you can implement trampolining. Functionally, it behaves the same as a hidden while loop and it is pretty much the same in terms of performance as well.

I’m not necessarily convinced that this approach has any additional benefit, and I personally feel it looks a little less friendly than a while loop. But it is probably ever so slightly more in accordance with the functional paradigm in that it dispenses with the while statement. Use this alternative version of trampolining if you prefer, but it’s a matter of personal preference, in my view.

This version is implemented using a C# command that under just about any other circumstance I’d implore you not to use. It has existed in coding since at least the days of BASIC and is still around in some form today: the goto command.

In BASIC, you could move to any arbitrary line of code you wanted by calling goto and specifying the line number. That’s often how loops were implemented in BASIC. In C#, however, you need to create tags, and it’s only to these tags that goto will move.

Here’s a reimplementation of IterateUntil() using two tags. One is called Loop​Begin⁠ning, which is the equivalent of the { character at the beginning of a while loop. The second tag is called LoopEnding, which represents the } character at the end of a while loop:

public static T IterateUntil<T>(
 this T @this,
 Func<T, T> updateFunction,
 Func<T, bool> endCondition)
{
    var currentThis = @this;

    LoopBeginning:

        currentThis = updateFunction(currentThis);
        if(endCondition(currentThis))
            goto LoopEnding;
        goto LoopBeginning;

    LoopEnding:

    return currentThis;
}

I’ll leave it to you to decide which version you prefer. They’re pretty much equivalent. Whatever you do, don’t go using goto anywhere else in your code unless you absolutely, positively, completely, and utterly know what you’re doing and why there’s no better option. Like a certain snake-loving, noseless, evil wizard, the goto command is both great and yet also terrible if used unwisely.

It’s powerful in that you can create effects and improve efficiency (in some cases) in ways that are impossible via any other means. It’s also dangerous in that you no longer have a predictable order of operations—during execution, the pointer can jump to an arbitrary point in the codebase, regardless of whether it makes any sense at all to do so. Used improperly, you could end up with inexplicable, hard-to-debug issues in your codebase.

Use the goto statement with great caution.

A third option, presented in the next section, requires quite a bit more boilerplate but ultimately looks a little friendlier than the previous versions. Have a look, and see what you think.

Summary

You’ve learned how to implement indefinite iteration in C# using the foreach statement, which results in cleaner code with fewer possible side effects of execution.

It’s not strictly possible to do this purely functionally. Several options are available, all of which carry some level of compromise to the functional paradigm. This is the nature of working in C#. Which option, if any, you wish to use is entirely a matter of personal choice and whatever of any constraints that apply to your project.

More often than not, I go with the trampolining option. It isn’t as dangerous as recursion, nor as much work to implement as a custom iterator. As always with these things, your choice depends what you’re trying to do. The requirements and constraints of your project will determine the best option.

Please be cautious with the use of recursion. It’s a fast method of iteration that’s purely functional, but if you aren’t careful, it can lead to significant performance issues when it comes to memory usage.

In the next chapter, I’ll show you a nice way to take advantage of pure functions to improve performance in your algorithms.