In the first post in this series, I provided a list of concepts that I found to be characteristic of functional languages. We’ve talked bout the first four so far.

• First Class Functions
• Higher Order Functions
• Pure Functions
• Currying or Partial Application Covered in the 2nd post.
• Recursion
• Pattern Matching
• Memoization

Updated: Thanks to Brad Wilson for recommendation to use !Any() instead of Count()==0.

Recursion

A recursive function is a function that calls itself. To quote Wikipedia,

“Recursion […] is a method of defining functions in which the function being defined is applied within its own definition”
- en.wikipedia.org/wiki/Recursion

In general, we programmers are shy about using recursion as it can easily lead to the dreaded stack overflow. However, recursion is crucial aspect of using functional languages. The problem of overflowing the stack can be avoided using something called tail recursion. But this post is not about explaining what recursion is, rather it is about explaining its role in functional languages.

Recursion is a mechanism for controlling flow. In fact, you’ll hardly ever see a loop when writing functional code; you’ll use recursion instead.

Let’s jump straight into an example. Consider our C# function Reduce from the first post:

static int Reduce(Func<int, int, int> reducer, IEnumerable<int> values)  
{  
    int accum = 0;  
    foreach (var i in values)  
    {  
        accum = reducer(accum, i);  
    }  
    return accum;  
} 

Now, we can define another function that produces the same output, but uses recursion instead of a loop:

static int ReduceF(Func<int, int, int> reducer, IEnumerable<int> values, int seed)
{
    if (!values.Any()) return seed; // #5

    var first = values.First();       // #1
    var remainder = values.Skip(1);   // #2
    var next = reducer(seed, first);  // #3

    return ReduceF(reducer, remainder, next);  //#4
}

The first thing to note is that ReduceF includes an extra parameter, seed. This new parameter plays a role analogous to the variable accum in the original Reduce. In order to have the same behavior as Reduce, we’d need to pass in an intial value of 0 for seed when calling ReduceF. Don’t get hung up on the extra parameter though. Let’s step through the logic.

1. Skipping over #5, we’ll come back to that. The first real step is to grab the first element in the list. We’ll use the extension method defined in System.Linq to do so. In functional terms, we’d refer to this as the head of the list.
2. Next we want to grab the remainder of the list. That is everything remaining after we’ve removed the head. The remainder is called the tail. Depending on the length of the list it might be any number of elements or it might be empty. Again, we’ll use a System.Linq extension method to skip over the first element and return the rest.
3. Here we apply our reducer function using the head of the list and the seed value. I named the value next because it will be the seed in our next call to ReduceF.
4. This is the recursive call. The reducer function is merely passed through. Notice though that we are passing remainder and next. Each time the function is called, the remainder has one less item. You’ll also see here how the seed parameter takes the place of our mutable accum variable from Reduce.
5. Eventually, we’ll pass in a list with no remaining items. When we detect that, we know that seed contains the final reduced value and so we return it.

If the code still doesn’t make sense, spin up a quick console application and execute this

Func<int, int, int> add = (i, j) => i + j;
var integers = new[] {1, 2, 3, 4, 5};
var sum = ReduceF(add, integers, 0);

and step through each call to ReduceF. Pay attention to the value of seed during each call as well as the count of elements in values.

Recursion Helps Us Avoid Mutable Data

We mentioned before that Reduce is a higher order function. Of course, the same is true for ReduceF. However, ReduceF is also more pure.

In our original Reduce, we maintained the state of our reduction using the variable accum. In each iteration of the loop we mutated the value of accum. At first glance, you might think that we are doing something similar in ReduceF. After all, we are defining even more variables inside of it. However, I added these superfluous variables just for readability. We can easily refactor ReduceF into

static int ReduceF(Func<int, int, int> reducer, IEnumerable<int> values, int seed)
{
    return (!values.Any()) 
        ? seed 
        : ReduceF(reducer, values.Skip(1), reducer(seed, values.First()));
}

All I did here was to replace the variables with the functions that I was using to set their values. (Well, I also threw in the glorious conditional operator too.)

Now we’ve done away with any internal state! Or, well, at least there is no mutable data. Technically we are still have a state, only it is now in the form of our seed parameter. We’ll see why this is vitally important when we begin discussing “why should we care about functional programming”.

Check out the comment from Irné Barnard under the first post to see an example of Reduce in Lisp.

Continue to Part 4.