Functional Programming in C#: Classic Programming Techniques for Modern Projects

RECURSION IN C#

The use of recursive algorithms in C# is restricted because for recursive function implementations, support for tail call optimization is something you want to rely on (see more about this in the next section). It is nevertheless important to understand the ideas of recursion. Doing so makes it easier to understand the limits of what can be done functionally in C#. And the transfer of algorithms from functional languages requires a good understanding of recursion — the result can often be worthwhile even if slightly different approaches have to be used in C#.

The following implementation of a factorial function is a simple first example of recursion:

static int RecFact(int x) {

  if (x == 0)

    return 1;

  return x * RecFact(x - 1);

}

The factorial of a positive integer is defined as the product of all positive integers smaller or equal to that integer. So, the factorial of 3 (written 3!) is 3! = 1 * 2 * 3 = 6. The factorial of 4 is 4! = 1 * 2 * 3 * 4 = 24. As you can see, there’s overlap in the calculations of those factorials. The factorial of any number n — fact(n) — can also be defined as n * fact (n - 1). For instance, fact(3) = 3 * fact(2). And fact(4) = 4 * fact(3).

The example implementation mirrors that simple rule precisely; the default return value of the function RecFact is x * RecFact(x - 1). The function RecFact is defined in terms of itself, which is the important defining factor for direct recursion (there’s also indirect recursion, which is explained ...