Introduction

Functional Programming , or FP for short, is an alternative approach to programming which is also available to you as a C# or VB.NET programmer: The fact that these languages are object oriented rather than FP-oriented doesn’t prevent you from coding recursive algorithms in them.

As I showed in the previous two articles in this series, FP can be characterized by:

• Very few variables are used, in particular dummy variables tend to be removed as much as possible.


• Recursion is used instead of iteration (e.g. for -loops).


• The program is built up from generic functions which are combined to form new, more specialized, functions


• In particular, functions are passed as arguments to other functions (these are then called higher order functions ).

With this technique, you can solve many common problems in programming in a very elegant way. Unfortunately, FP has not been used that much outside the world of academia. This is partly because the FP languages used at one time to be very inefficient and resource hungry – that’s something that, with modern languages, compilers, and computers, is no longer an issue. But the biggest obstacle to using FP efficiently is probably the need to rely on recursion instead of iteration. Although recursion has been available in all mainstream programming languages since the 60’s, it is still often treated as an advanced, or at least non-standard, topic. Many text books only have a brief chapter on the topic towards the end of the book. This leaves the novice programmer with the impression that recursion is far too advanced, impractical or academic to use in day to day programming.

It is true that in many ways, iteration is simpler than recursion. Iteration is closer to how the hardware is organized – some assemblers even have a for -loop built-in. Not only that but iteration is easy to program and can usually be implemented very efficiently.

Recursion, on the other hand, is perhaps a bit more high level. It certainly abstracts more from the underlying hardware than does, for example, C++. And it used to be that FP languages, relying heavily on recursion, were terribly slow compared to an iterative solution in a language like Fortran, Pascal or C. Object orientation does also incur an extra overhead, but this is usually negligible on modern computers. Similarly, modern FP compilers can generate code which is just as efficient as C++. This is partly because the functional style allows the compiler to carry out some extra optimizations which are not available to a C++/C#/Java compiler.

Anyway, modern computers are big powerful beasts with lots of RAM and very fast CPU’s. So even though a functional program written in a non-FP language like C# may be slightly slower or more memory hungry than a standard C# program, this can be easily outweighed by increased code re-use and simpler, more elegant algorithms. Just like managed code is sometimes slower than native code, this overhead is generally outweighed by the increase in productivity and code re-use.

In this article, then, I’ll show you how to "think recursively". I will do this by showing you how to re-write iterative code. I’ll start by re-writing a few code snippets, and then turn to a more complete program involving string manipulation. Along the way, I’ll introduce you to a few more ideas from the FP community and extend the FP library built in the previous articles with a few more utilities. Unfortuanately, because C# is designed as an object oriented language and doesn’t always have the best syntactic constructs to support FP, some of the code is going to look a lot more cumbersome – certainly compared to if you were using an FP language – but in this article it’s the concepts that are important.

System Requirements

The code I’ll present here is standard C# code and will run on any Windows box with .NET. 1.1 installed. You can open the solution file with Visual Studio 2003 or SharpDevelop. I haven’t tried it under Mono on Linux, but I have no reason to believe it won’t run there too.

Installing and Compiling the Sample Code

The sample download contains a VS.NET 2003 solution file that contains the original, non-FP program as well as the recursive version. It also contains updated versions of the library developed in the previous two articles. It can be installed anywhere on your PC.

The solution file contains a few differences from that of the previous two articles. A new class, Converter , has been added to the DataStructures project. Converter is meant to contain utilities for converting from one data type to another (in this case just from strings to lists and vice versa). It is my FP analog of the standard System.Convert -class.

From iteration to recursion

The most common example of recursion is probably the factorial function. In many text books this is even more or less the only example. The simplest version in C# (ignoring error handling etc) is just this:

public static int fact(int n) 

{
   if (n  1)
      return 1;
   else
      return n*fact(n-1);
}

But there's a long way from this simple function, to the code you probably normally write. I will go through the concepts rather slowly at first, looking at small code snippets and general strategies before I move on to a more complete application that demonstrates the FP approach.

In this section I'll dissect the simple for loop to show how you can approach the loop recursively.

Simple Loops using Iteration

I don't think I've ever written a program (besides pure FP ones, of course) which does not contain at least one loop. Often this is just a simple counting loop, like this

for (int i = 0; i < 100; ++i) {
  // do something
}

The variable i is usually just a dummy variable, which is merely there for house keeping purposes, to make sure that the operation is carried out the correct number of times.

A more complicated loop, where the next value of the dummy variable is actually calculated (possibly as the result of a very complex function) in each iteration would typically have the form

int i = 0;
while (SomeFunction(i)  true) {
  // do the loop processing during which the value of i is modified somehow

}

C# often allows the first kind of loop to be simplified by using a foreach -loop instead, which can then be simplified further using one of the higher order functions I introduced in my second article. I can always arrange to have the body of the loop consist of a single call to some function, let’s call it f . The code for the first loop is now:

for (int i = 0; i < 100; ++i) {
    f(i);

}

Let’s now consider how we need to view this loop in order to treat it as a recursive, rather than an iterative, process.

Towards Recursion: Listing the Counter Values

In symbolic notation, what I’d like to write is this

// Not valid C#!!!!

foreach (int i in [0..99]) { 
    f(i);

}

Here, [0..99] is supposed to be an anonymous list consisting of the range of integers 0..99 (both inclusive). Of course, C# doesn’t (as yet) support this, so to make life easy I’ll open up the FunctionalProgramming namespace I defined in the previous two articles and add a public static range() method to the Utils class. You’ll find this namespace in the FunctionalProgramming.DataStructures project in the code download. The range() method is a nice general feature to have, so it makes sense to put it there. To make life really easy, I’ll add a couple of overloads:

• range(int max) returns the list [0..max]


• range(int min, int max) returns [min..max ]


• And finally range(int min, int max, int step) returns the list consisting of [min, min+step, min+2*step, max] , where max need not be included and where step may also be negative.

This ought to cover most of our needs for now. Later you can add further overloads allowing for ranges of characters or floats, but I won’t do that now.

All of the work is to be done in the third, most general overloaded version of this function. Let me first do this in a normal procedural (i.e. non-recursive) way. C# makes it fairly easy to do this:

// standard C# way

public int[] range(int min, int max, int step) {
   if ((max <= min && step >= 0) || (max >= min && step <= 0))
       return null;
   int len = 1 + (max-min)/Math.Abs(step);
   int[] res = new int[len];
   for (int i = 0; i <= len; ++i )
      res[i] = min + i*step; 
   return res;

}

But, I will, of course, choose a recursive algorithm instead. Here’s how you can do that:

Coding the Loop Recursively

The next task is to rewrite the loop in a recursive way. And while I’m at it, I’ll also let it return a FunctionalProgramming.DataStructures.IRecursiveData instead. This interface was defined in the first article, it provides methods for accessing the first, "head", element and the remainder (the "tail"). I can re-formulate the algorithm like this:

• If step > 0 && min > max or step < 0 && min < max then I’m done and I just return null


• Otherwise, create a single element list consisting of min


• Add step to min , and recurse adding the result to the single element list.

The code is pretty obvious and doesn’t present any challenges.

namespace FunctionalProgramming

class Utils {
 // existing stuff 
#region —- ranges —-
   public static IRecursiveData range(int min, int max, int step) {
      IRecursiveData rsd = null;
      if ((min > max && step > 0) || (min < max && step < 0))
         return null;  // nothing to do
      rsd = new FPList(min) as IRecursiveData;
      return cons(rsd, range(min + step, max, step));
   }
   public static IRecursiveData range(int min, int max) {
      return range(min, max, 1);
   }
   public static IRecursiveData range(int max) {
      return range(0, max, 1);
   }
   #endregion

}

The class FPList was defined in the first article, it is an implementation of a singly linked list implementing the general IRecursiveData interface.

The main difference between the two solutions is that the recursive one gets rid of the dummy variable i . Instead it relies on the runtime stack. Otherwise they are very similar. For problems this simple, neither approach presents any big advantage, other than that in the FP case the list of values needs to be allocated, which could hit performance. An FP language would on the other hand offer additional compiler optimizations not available in to the C# compiler.

Notice, by the way, that giving a step size of zero will cause an infinite loop. This is not an error – techniques for handling infinite data structures in FP exist but are beyond the scope of this article. For now, I’ll just leave it in for simplicity. If you plan to use the code already, you should add a throw statement raising an ArgumentException if step 0 .

With this in place, I can finally write the symbolic code above in correct C#. Anyway, I find it useful to sometimes take a break and reformulate what I'm about to do. In plain text, when I write a normal for loop I'm doing the following.

• Initiate the counter ( int i = 0 )
• If the counter is below the limit, evaluate the function on the counter
• And calculate the next value of the counter
• And repeat everything except the first point
• Stop if the counter value becomes too big.

This can be reformulated in terms of recursion by letting the function take a list of values (in the simplest case just a range) as its arguments, instead of taking just a single value. Like this

• If the input list is empty, return
• Otherwise, apply the internal function to the head of the list (i.e., its first element)
• And apply the entire procedure to the tail of the list (i.e. the remainder of the list).

Finally, I can implement this in C# like this

void f_rec(IRecursiveData rds) {
   if(rds  null)
      return;              // nothing more to do
   f(Utils.head(rds));      // apply to first value
   f_rec(Utils.tail(rds));  // and recurse

}

Using Higher Order Functions

What I’ve shown you in the previous section is the simplest way to transform an imperative for -loop into a recursive FP function body. For each loop, you would then have to define a recursive function. This is not really efficient and would lead to an enormous amount of code duplication. Instead, you can wrap it all up in a single line by using the higher order function map() from the second article in this series (recall that a higher order function is function taking another function as an argument and/or returning a function). The map() function was defined using FP pseudo code like this:

map f [] = []

map f (x:xs) = f(x) : map (f xs)

Let me quickly summarize the notation. Functions can be defined as a series of special cases, and the compiler will pick the most accurate special case. This is the way template instantiations work in C++ or template matches in XSLT. Now in this notation [] denotes the empty list, while (x:xs) denotes the list with x as its first element (the head) and xs as the, possibly empty, remainder (the tail). Finally, the colon denotes list construction .

Using this, you can instead just write the following:

Utils.map(new Utils.unary(f), new Utils.range(99));

Higher order functions are the glue of FP, they are the prime mechanism behind code re-use, and they are also the basic abstraction mechanism. To summarize, what you just did was to look at a simple iterative construction (a for -loop), (1) You then rewrote this as a recursive function, (2) then you recognized a common structure, (3) this common structure was then abstracted out into a higher order function. Well, in this case, you had already written that higher order function. Otherwise, you would have written it at this point. In any case, it was rewriting it using recursion that revealed the common structure.

But all of this only works if the function f does not change its parameter – just like the standard foreach -loop will throw an exception if you modify the iteration variable. If you want to allow f to change the parameter i , you’ll have to use the while -loop in standard C#. Or resort to recursion. And of course, this series being about FP, this is precisely this option I’ll pursue here.

To do this, let’s first of all rewrite the while -loop to look as much as possible as the original for -loop. One way of doing this is like this:

int i = 0;

while (i < 100) {
   i = f(i);

}

You could have written just f(ref i) instead of i=f(i) , if you had defined f to take a ref parameter, but I generally don’t like that – I prefer functions to have as few side effects as possible. In general, in FP, you’re not allowed to have any kind of side effects. This makes it easier for the programmer (and the compiler) to understand the code. My personal rule of thumb is to avoid ref or out -arguments unless I have to use them, e.g. when calling a legacy COM method.

There’s probably many different ways to turn such a while-loop into a recursive function or into an application of a higher order function (which is then recursive under the hood). But there is one way that jumps at you, when you start thinking about the problem. Notice that the function f when given one value of the counter will return the next value to be used. So, one way to proceed is to continue the recursive process with this return value as its input. Actually, this is the idea behind what I would call a functional design pattern , namely continuation passing . You can turn this into a very sophisticated (and complicated) way of programming, but I’m going to be simplistic here, and go for the simplest possible implementation of continuation passing. Like this:

void whilef(int seed, int max) {
   if (seed >= max)
     return;                // done
   whilef(f(seed), max);      // compute next value, and recurse

}

To start the processing, this function must then be invoked as whilef(0,100) .

Again, although this works, it is not really satisfactory. It is no good having to write a new function for each function you want to loop over! There must be a higher order function hidden here. And indeed there is. Several, in fact.

The simplest approach would be to let whilef take the function f as an input parameter. Let’s call this higher order function while_rec to remind us that is a recursive analogue of a while -loop. Its definition is quite simply

void while_rec(Utils.unary f, int seed, int max) {
   if (seed >= max)
      return;                      // done
   while_rec(f, f(seed), max);     // recurse

}

Not exactly the stuff of legends. It’s a bit clumsy to have to pass the function (delegate) f around in the recursive step, but C# does not support local functions , in a proper FP language, you could write something like this

while_rec f seed max = let do_rec count max = 
                     if count >= max then 
                               return 
                            else 
                               do_rec f(count) max 
                        in 
                            do_rec seed max

In general, I find the best analogue of this in C# is to use a private helper function. But this won’t work in this case — this helper function would just be a duplicate of whilef() above and you would have to write one such helper function for each function you’re going to loop over. Not an option for a big, complicated project!

Using Recursion in String Processing

So far I have shown you a few ways to re-write an iterative program snippet using recursion and higher order functions. I also threw in a new utility method, Utils.range() , just for good measure. That might be enough to get you started writing FP-style programs in C#. But to guide you further on your way, I’ll show how to apply these ideas to a concrete program.

I’ve tried to come up with a sample application that was (a) simple enough that I don’t have to explain very much, (b) common enough that it might actual be useful, and © easy to write in the normal imperative way. Well, here’s what I came up with. Suppose you want to write an application to find the longest common substring of two strings. Let’s first see how you could code this iteratively:

Finding Matching Substrings using Iteration

One reasonably straightforward way of doing this would be like this:

private static string LongestCommonString_Iter(string s1, string s2) {
   int len1 = s1.Length;
   int len2 = s2.Length;
   string best = "";  // the longest common substring found
   //starting from the beginning of s1, 
   //loop through it finding common substrings
   for (int i = 0; i < len1; ++i) {
   for (int l = 0; l < len2; ++l)  {
      string temp = "";  // a guess at a candidate
      bool found = false; // not found yet
      int j = 0;  // offset in the second string
      // find location of first match
      while (!found && l+j < len2) {
         if (s1[i]  s2[l+j]) {
            found = true;
            temp = s2[l+j].ToString();   // found something
         }
         ++j; // try next character
      }
      // find matching substring from here
      if (found) {
         int k = 1; // relative position along the first string
         bool same = true;
         while (same && l+j < len2 && i + k < len1) {
            if (s1[i+k]  s2[l+j]) {
               temp += s2[l+j]; // still matching
            } else {
               same = false;
            }
            ++k;
            ++j;
         }
      }
      // how did we do?
      if (temp.Length > best.Length)
         best = temp;
   }
   }
   return best;

}

This code contains quite a few loops and dummy variables (the string temp , the Boolean flags found and same , the integers i , j , k ). Given some more time, you could probably have improved the algorithm or written the code more concisely, but that is not the point here. My only reason for writing this code is to illustrate how to turn standard iterative code into recursive FP-style code.

So, how could you re-write this using recursion?

Converting strings to lists

My first step is actually not to touch the code at all, but instead note that all my FP-tools work on IRecursiveData and not on System.String objects. But a string is really just a list of characters, so my first task is to write a general converter, transforming a string into an FPList of single characters.

I will add yet another utility class to the project. This time I’ll call it Converter , and in it I will have two static methods having the dynamic names explode and implode (these are common names for these functions in other FP languages). Here is the actual code:

namespace FunctionalProgramming.DataStructures {
  /// <summary>
  /// Misc. conversion routines
  /// </summary>
  public class Converter {
    // convert a string to FPList of single characters (as strings)
   public static FPList explode(string s)    {
        if (s  null || s  String.Empty)
      return null;
     else if (s.Length  1)
      return new FPList(s);
     else  
       return (FPList)Utils.cons(s.Substring(0,1),
                                explode(s.Substring(1)));
   }
   // convert a FPList to a string by concatenating elements
   public static string implode(FPList list) {
     if (list  null)
      return String.Empty;
     else
      return Utils.head(list).ToString() +
             implode((FPList)Utils.tail(list));
   }
  }

}

The only subtleties here are (1) the use of recursion, but you are probably getting used to that by now, and (2) the use of Substring() . In C#, s[i] is a System.Char and cannot be implicitly converted to a string, while s.Substring(i,1) is a one character System.String . Similarly, Substring(1) is the System.String equivalent of my general Utils.tail() method.

With these two utilities at hand, the problem has been transformed into one of finding the longest common sublist of two lists. You see how an added bonus of this approach is that the method I’ll end up with is more general than the original iterative function. This is a "side effect" of the increased level of abstraction at which FP works – you start up trying solve to a concrete problem and end up with more general functions, which you can re-use for other problems.This is a common way to solve problems in FP, combining a "divide and conquer" strategy on the one hand with an "increase the level of abstraction" strategy on the other.

Writing the generic function(s)

This is the last bit I need. The iterative algorithm above solves the problem by looping over the two strings, and finding the first matching substring from that given pair of positions. Moving along a string can be translated into recursion on the tail of the list of characters. Furthermore, the algorithm has to find all common substrings anyway, so one approach would be to have a function find these, and then later picking the longest one. This would be another functional design pattern or idiom – you return a list of all solutions and then let the user at a later stage pick which one (s)he wants.

The advantage of this approach is that you write a very general function, which can later be used, when you want to find, say the shortest common substring. The disadvantage is, of course, that it takes more memory to store the complete list of solutions than it does to store the best solution found so-far. But then again, if I only store the best match found up till now, I will have a harder time re-writing the program later when someone comes along and asks for the smallest common substring as well. I think the best solution is to go for the more generic approach when you are sure your lists or strings are not going to be too big, and go for the other solution when you need to deal with very long lists.

Anyway, having used the "increase the level of abstraction" strategy to get this far, I’ll start using the "divide and conquer" one for a while. When I’m looping through the two input lists looking for matches, what I am in fact doing is to look for the longest common sublist from the start. So what I’ll be looking for is where the two lists begin to differ. Hence, my first function will be one that keeps picking elements from the start of two lists as long as they are identical and returns this constructed list. For instance, if I give it two lists [a,b,c,d] and [a,b,x] it will return [a,b] .

This is a generic function, so I’ll put it inside the Utils class so I can re-use it later. The code is

public static IRecursiveData same(IRecursiveData lst1, IRecursiveData lst2){
   if (lst1  null || lst2  null)
      return null;   // special case to make recursion terminate
   object h1 = head(lst1);
   object h2 = head(lst2);
   if (h1.Equals(h2))
      return cons(new FPList(h1), same(tail(lst1), tail(lst2)));
   else
      return null;

}

It is not very subtle code. I first look to see if any of the two lists (or RDS’s – Recursive Data Structures — in general) are empty, if so I’m done and just return null . Otherwise I look at the two heads, if they are identical, I add the value to a list and recurse on their tails, if not, I’m again done and return null .

Notice, by the way, that there is a new higher order function hidden here. You could replace the test for identity with a general Boolean function of two arguments, but you don’t need that level of generality here, so I won’t do anything further about it.

This function performs the same role as the iterative loops involving the Boolean same -flag (whence the name). What I need now, is something corresponding to the two outer for -loops. Here you need to recurse on the tails of the two strings independently , whereas in the function same() you recursed on them simultaneously .

In the innermost loop, the first string is fixed, while the other is looped through. This would result in a list of sublists. This can certainly be done, but I think it is easier to simplify by instead returning a list of strings. This suggests a helper function common2 looking like this

private static IRecursiveData common2(IRecursiveData lst1, 
                                      IRecursiveData lst2) {
   if (lst1  null || lst2  null)
      return null;
   else {
      string sub = Converter.implode((FPList)Utils.same(lst1, lst2));
      if (sub  null || sub  "")
         return common2(lst1, Utils.tail(lst2));
      else
         return Utils.cons(sub, common2(lst1, Utils.tail(lst2)));
   }

}

This is a helper method, which I don’t expect to re-use elsewhere, so I’ve declared it private and defined it inside the StringApplication.Main class (where the iterative solution can also be found). The function loops through the second list, and for each recursive step it calls Utils.same() . If this results in a non-empty string I add it to the results list, otherwise I just move on to the next step.

My next task is to repeat this by looping through the first string. The code is very similar, but instead of calling Utils.same() at each step, I must call the newly defined common2 function. And, of course, I must recurse not on the tail of the second list, but of that of the first. I call the function common1 , and it looks like this.

private static IRecursiveData common1(IRecursiveData lst1, 
                                      IRecursiveData lst2) {
   if (lst1  null || lst2  null)
      return null;
   else {
      IRecursiveData res = common2(lst1, lst2);
      if (res  null)
         return common1(Utils.tail(lst1), lst2);
      else
         return Utils.cons(res, common1(Utils.tail(lst1), lst2));
   }
}

This then gives you the complete list of common substrings. I'm almost done now, all that remains to do is the pick the want you one.

There are many different ways you could do that. You could sort the list in descending order, and pick the last element. Or you could sort it in ascending order and pick the head. Yet another way is to use an accumulator parameter . This is also a kind of FP design pattern very similar to continuation passing. The way you'll use it here is actually a special case of the way you used continuation passing earlier. It has the advantage of being very similar in spirit to the iterative code. Just like you used a variable best to hold the best match found so-far, you can use an accumulator parameter seeded with the empty string in an FP version. This is how you can do it:

private static string pickLongest(IRecursiveData lst, string acc) {
   if (lst  null)
      return acc;
   string hd = Utils.head(lst).ToString();
   if (hd.Length > acc.Length)
      acc = hd;
   return pickLongest(Utils.tail(lst), acc);

}

Finally, you just put the pieces together:

private static string LongestCommonString_rec(string s1, string s2) {
   IRecursiveData rsd = common1(Converter.explode(s1),
                                    Converter.explode(s2));
   return pickLongest(rsd, ""); // initial guess is ""

}

Further Work

You can go in many different directions from here. I’ve already mentioned functional design patterns , and whole volumes could be written on this in general or on continuation passing in particular. Just like the OOP community has identified a series of design patterns, starting with the Gang of Four, so has the FP community. The basic ingredient in OO design is probably inheritance. In FP it is higher order functions. Once you get used to the FP-style, you’ll begin to see higher order functions everywhere.

I’ve also mentioned infinite data structures . This is actually one such FP design pattern, if you wish. It is called lazy evaluation , and it is similar to what the .NET framework does when it executes MSIL code – if it hasn’t seen that particular code snippet before, it compiles it to native code, otherwise it already knows the native assembler code and just executes that instead.

Then there’s of course adding more applications. The obvious one to add, I guess, would be XML manipulation. This is a subject that lends itself very well to an FP treatment. After all, it is based on a tree, which, as I showed in the previous article, is an example of a RDS (Recursive Data Structure). And this is of course also the reason why the standard XML manipulation language, XSLT, is a functional language.

Finally, there’s the experimental FP languages designed by Microsoft, Cω (C omega) and F#. Actually, Sun is also toying with an FP language for the Java platform. The two languages from Microsoft are both designed for the .Net platform. The first is an extension of C# adding many FP-like features, while the second is a port of one of the main FP-languages to .Net. F# is very similar to the "FP pseudo-code" used in this series, by the way.

Conclusion

This article mostly built on what was done in the previous two articles, but I did introduce some utilities and some new concepts (such as continuation passing). I showed you how to turn standard iterative C# programs into FP-style ones. In principle, an advantage of doing so is that you end up with arguably more elegant code, although if you are using C# this is hampered by the lack of support in C# for FP constructs. During the process of "translating" from OOP style to FP style, you saw how to identify some generic functions to do the job. These can be easily re-used elsewhere. This a direct result of the "refactoring" done by translating the original program into FP-style.