Sponsored By Aspose - File Format APIs for .NET

Aspose are the market leader of .NET APIs for file business formats – natively work with DOCX, XLSX, PPT, PDF, MSG, MPP, images formats and many more!

Define Recursion – See Recursion

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.

This entry was posted in C#, F#, Functional Programming. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • http://www.managed-world.com jolson88

    @Matt

    LOL, yeah, I noticed that. Oh well :).

  • http://podwysocki.codebetter.com Matthew.Podwysocki

    @Ralf

    True, unless it’s a tail recursive function, then it could go infinitely and I’m not sure you want that. But if you’re talking linear recursion, binary recursion and so on, absolutely, it will fail fast.

    Matt

  • http://podwysocki.codebetter.com Matthew Podwysocki

    @Jason

    Pesky comment emoticons!

    Matt

  • http://podwysocki.codebetter.com Matthew Podwysocki

    @Jason

    Yeah, Haskell and Erlang have very nice shorthand for doing those operations. To do something similar in F# would look like this:

    let rec remove x l =
    match l with
    | [] -> []
    | h::t when h = x -> t
    | h::t -> h:: remove x t

    let rec permutation xs =
    match xs with
    | [] -> [[]]
    | _ -> [for x in xs
    for ys in permutation (remove x xs)
    yield x::ys]

    [1..3] |> permutation |> print_any

    It still works, but not as elegant. Recursion is indeed a fun topic!

    Matt

  • http://ralfkret.blogger.com Ralf Kretzschmar

    One more advantage of recursion over iteration: If you get your exit condition wrong, a recursive algorithm will fail fast with a stack overflow exception.
    And on using recursion for walking (I just try to not to use the term iterating) a list: Have a look at the parse class from the Fit.Net library. It opened my eyes on how elegantly use lists.

  • http://www.managed-world.com Jason Olson

    Matt, I have no luck clicking the “add” button for adding a comment in IE7 (not sure if you know about that or not).

  • http://www.managed-world.com Jason Olson

    Ahhhh, I love me a good cup of recursion :P. As you showed with your examples of F#, getting into a functional programming language is a great way to really start to see the power of recursion.

    I personally like how Erlang uses recursion. For instance, the Factorial function (hopefully the HTML formatting doesn’t eat my code):

    Factorial(0) -> 1;
    Factorial(N) -> N * Factorial(N-1).

    What REALLY warps my noggin’ is when you start combining list comprehensions with recursion. For instance, code that generated all anagrams of a given sequence of letters/numbers would be the following in Erlang (for instance, for 123, it would generate 123, 132, 213, 231, 312, 321):

    perms([]) -> [[]];
    perms(L) -> [[H|T] || H <- L, T <- perms(L–[H])].

    Now _that’s_ a mind-bender :).

    Rock on Matt!

  • http://podwysocki.codebetter.com Matthew Podwysocki

    @Scott

    Well played sir. LOL!

    Matt

  • http://www.lazycoder.com Scott

    For more on recursion, see this post. http://tinyurl.com/6bxyb5