Lately, I've noticed a few blogs are doing the come back to basics post, such as
Scott Hanselman's. I think that's an effort that should be lauded, because many have a tendency to go off on pretty advanced topics, yet not provide enough for those just starting to get the full context. So, with that, I'm going to dig into one piece of programming that should have been ingrained should you have been a CS major in college or at least took some courses.
Recursion
Recursion is one of those basic topics that come up time and time again as one of the core topics. It's not as often talked about in the imperative and object oriented world, but in the functional programming world, it matters a whole bunch. Not only to be able to describe what it is, but the benefits, and where you might be able to break your problem down into using it.
So, before we get too far, what exactly is it, and how do we get there? Basically recursion is to allow a function to call itself repeatedly during the body of that function. Most imperative languages from the C world use for loops, while loops and so on, so many times recursion isn't needed. Functional languages such as F#, allow for recursion, but makes them a special designation to enforce its behaviors.
When coming to a place such as Microsoft, understanding these concepts are key. Chances are you may get asked some of these questions, because people like me, when walking through complex structures, use recursive algorithms. It's a nice tool to have in the toolbox.
Let's first look at an example not using recursion, then move towards recursion. First start off with a pretty obvious one in computing a factorial:
public static int Factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
To me, that's pretty horridly imperative. We can make the code much more concise through the use of recursion and not mutate state during the operation. With the proper attention of course to decrementing the counter so that we don't get into infinite loops. An important lesson to learn is to not recurse infinitely, but in a controlled manner towards termination through a technique called
"Well Founded Recursion". Let's rewrite this to a much more manageable way:
C#
public static int Factorial(int n)
{
if (n <= 1) // Exit condition
return 1;
return n * Factorial(n - 1);
}
F#
let rec factorial n =
if n <= 1 then 1 else n * factorial (n - 1)
The basic idea is to break down your problems into smaller instances of the same problem. Sometimes, the last thing we do in this function is return the recursion of the function. This is called
"Tail Recursion". Below is a simple example of tail recursion:
let rec last l =
match l with
| [] -> invalid_arg "l"
| [head] -> head
| head :: tail -> last tail
The above sample will ultimately give me the last item in a list since F# has pointers to the head of the list, we need to get the last one. We'll get more into tail recursion in the next post, but I thought I'd introduce it now. It's very important as well to know.
Let's take another example, this time walking a directory structure to lazily display all files in a directory. Of course we can note that the Directory.GetFiles already has the capability of getting all files in all folders, but for this exercise, let's pretend it doesn't exist. How might we do this? Let's try the lazy approach the first time around through IEnumerable<string>.
C#
public static IEnumerable<string> GetFiles(string rootPath)
{
foreach(var file in Directory.GetFiles(rootPath))
yield return file;
foreach (var directory in Directory.GetDirectories(rootPath))
foreach (var file in GetFiles(directory))
yield return file;
}
F#
let rec getFiles rootFolder =
seq {
for file in Directory.GetFiles(rootFolder) -> file
for dir in Directory.GetDirectories(rootFolder) ->> getFiles dir
}
What this allows me to do is recurse through a given directory hierarchy by first grabbing all the files and then going through a tail recursion through all the subdirectories. The F# way is a bit more concise through the use of Sequence Workflows, which I'll get to at another time. If you understand anything about F#, understanding workflows is by far one of the most important.
Mututal Recursion
Another interesting way to express recursion is to define them simultaneously by separating the definitions. This allows the functions to play off each other and work towards a deterministic end. The cannonical example of this is the odd/even sample. Let's walk through that quickly in both C# and F#:
C#
public static bool IsEven(int number)
{
if (number == 0)
return true;
else
return IsOdd(number - 1);
}
public static bool IsOdd(int number)
{
if (number == 0)
return false;
else
return IsEven(number - 1);
}
F#
let rec even n = (n = 0) || odd(n - 1)
and odd n = (n <> 0) && even(n - 1)
As you can see, I decrement the counter each time and call the complement function until I reach 0 and at that point, I can determine which one hits 0 and then it becomes apparent whether it is odd or even. F# goes a bit further to simplify this so that I can declare those functions as a pair through the use of the and keyword. Parsing of trees is particularly useful using mutual recursion. But just as easily, we could have done the above sequence without using recursion at all such as this:
public static bool IsEven(int number)
{
return number % 2 == 0;
}
public static bool IsOdd(int number)
{
return !IsEven(number);
}
So, that's not really a good example. instead, let's look at a
Hofstadter Male-Female Sequences instead.
The pair of sequences is defined by Female(0) = 1 and Male(0) = 0 and
Female(n) = n - Male(Female(n - 1)
Male(n) = n - Female(Male(n - 1)
This is defined as the same way as before, but we recursively call in the Male to the Female and back to the male, whereas it's the opposite in the FemaleSequence method. This is just a simple implementation of the above algorithm in our C# and F# code respectively.
C#
public static int MaleSequence(int n)
{
if (0 == n)
return 0;
return n - FemaleSequence(MaleSequence(n - 1));
}
public static int FemaleSequence(int n)
{
if (0 == n)
return 1;
return n - MaleSequence(FemaleSequence(n - 1));
}
F#
let rec maleSequence n = if n = 0 then 0 else n - femaleSequence(maleSequence n - 1)
and femaleSequence n = if n = 0 then 1 else n - maleSequence(femaleSequence n - 1)
There are more examples out there, but in the mean time, there's plenty more to cover with recursion. Next, let's cover lists.
Walking Lists
Another thing we can do with recursion is the ability to walk lists. Most people think of lists as an ordered collection with a beginning and an end, with one right after another. How terribly imperative if you think that way... When we think of lists in a recursive way, we think of a list to have an item, and the rest of the list, or just an empty list. C# and the base class library does not have this of course defined in any meaningful way, so let's look at the F# version of a list.
module List =
val hd: 'a list -> 'a
val tl: 'a list -> 'a list
What that tells us is that the head item is the first, and the tail is the rest. Let's do a quick recursion to calculate the length of a list using some pattern matching:
let rec length l =
match l with
| [] -> 0
| head :: tail -> 1 + length tail
What I'm doing is pattern matching against the list. What the pattern matching allows me to do is short circuit if it's an empty list, else, I'm splitting the head and the tail, and adding one to the length of the tail call with the tail of the list. Let's look at another to concat a list of lists into a single list:
let listOfList = [[1;2;3;];[4;5;6;];[7;8;9]]
let rec concatList l =
match l with
| [] -> []
| head :: tail -> head @ concatList tail
There is much more to cover here and I'll do that in subsequent posts.
Why Recursion?
Now that we covered some of the basics, it's time to ask the question why. Why is recursion important and why use it? Well, to answer that lightly, in order to walk such things as trees, directories, and so on, it's an absolute essential. But, let's consider just a general functional programming question of why use it.
It's often the case that when people first start out with programming in F#, they are often in the imperative and OO mindset still. That's ok since F# allows for this, but there are better ways to accomplish in the functional mindset. Many times, people will port over their C# code directly to F# with the mutable variables or reference cells and leave an ugly mess. Some of that can be solved with recursion. Let's take a pretty naive example:
C#
public static void CountDown(int n)
{
while(n > 0)
{
DoOperation();
WaitSome();
n -= 1;
}
}
When translated directly to F# looks like this:
let countDown n =
let mutable localN = n
while localN > 0 do
DoOperation()
WaitSome()
localN <- localN - 1
What we've had to do is use reference cells so that we could change the value of n directly. From there, we have to use special operators to change and alias the value of n. Not the prettiest code. Not only that, but there is mutation galore, and I have to do extra work when creating a local iterating variable. instead, we should focus on recursion and look at the problem slightly differently.
let rec countDown n =
match n with
| 0 -> 0
| _ ->
DoOperation()
WaitSome()
countDown (n - 1)
What this allows me to do is get rid of the local mutables, but also helps me break my problems into smaller, more similar problems which can be recursed. This allows for better code reuse and maintenance I think.
Wrapping It Up
I'd like to spend some more time with tail recursion as I think it's pretty important. As well, I'll also talk about how you can do the same in C# as well (with a little work of course). But in the mean time, I hope I've demonstrated the simple act of recursion, when to look for it, and how to exploit it. Not all problems are ready for recursion, but when you find the right opportunities for them, it's quite powerful.