INDIRECT RECURSION

So far, all of the recursion examples have had one thing in common: one single function involved that called itself, which is called direct recursion. There is also indirect recursion, where several functions depend upon one another. For instance, function A calls function B, which calls function C. If function C, under any circumstances, calls back to function A, this is a case of indirect recursion.

There is a simple case of indirect recursion called mutual recursion. It involves only two functions that depend upon one another. In reality, the logic behind the dependency can be quite complex. Nonetheless, here’s an example that involves odd and even numbers:

static bool IsOdd(int number) {

return number == 0 ? false : IsEven(Math.Abs(number) - 1);

}

static bool IsEven(int number) {

return number == 0 ? true : IsOdd(Math.Abs(number) - 1);

}

As you can see, the definition of an odd integer is this: if the number is zero, it is a known fact that the number is not odd. Otherwise, the number is odd if the number before it is even. The definition of an even number is exactly the other way around: zero is known to be even, otherwise a number is even if the number before it is odd.

The two functions IsOdd and IsEven depend upon each other; they are therefore called mutually recursive. The example scenario also has two different base cases that are checked in the two functions. Obviously, this can get quite complex — if you employ code ...

Get *Functional Programming in C#: Classic Programming Techniques for Modern Projects* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.