Recursion Primer Using C++, Part 1

1. Introduction

In general, recursion means self-repeating patterns. In mathematics, it can be a function that is defined in terms of itself, such as factorial, Fibonacci, and so forth. In computer programming, recursion means a function that is defined in terms of itself. In other words, it is a function that calls itself. Every recursive function has a termination condition; otherwise, it will call itself forever, and this condition can be called a base condition.

Usually, recursion is a little bit difficult for most students to understand. Researchers usually come up with different strategies to teach recursion easily for students, such as teach recursion before arrays [4], delegation [2], or recursively generated geometric designs [3].

2. Types of Recursion

In C++, the types of recursion can be defined in more than one dimension. In one dimension, it can be categorized as run time recursion and compile time recursion using template meta-programming.

Run time recursion is the most common recursion technique used in C++. This can be implemented when a C++ function (or member function) calls itself.

In C++, we also can do compile time recursion with the help of template meta-programming. When you instantiates the template class (or structure) in C++, the compiler will create the code of that class at compile time. Just like run time recursion, you can instantiate the template class itself to perform the recursion. Just like run time recursion, you also need the termination condition; otherwise, instantiation will go forever, at least theoretically, but of course it is limited to the resources of the computer and compiler. In this meta-programming template, you can specify the termination condition (or base condition) with the help of template specialization or partial template specialization, depending on the termination condition.

One can thing that might do the same thing with the C++ preprocessor is to use macros because they also will replaced during compilation. In fact, technically a preprocessor replaces all the macros even before compilation, so it is not performing at compile time. The preprocessor also has lots of limitations; because of simple text replacement, there is no debug symbol define for the debugger, but the most critical limitation is that it can not be recursive. The section 16.3.4.2 standard of C++ [1] strictly restricts one to write macros that call themselves recursively; therefore, you can’t do recursive programming in macros, just like you used to do in template programming.

The other way to see the recursion is by how the recursive algorithm is implemented. A recursive algorithm can be implemented in more than one way, such as linear, tail, mutual, binary, or nested recursion. You can implement them either at compile time using template meta-programming or at run time using function or member functions.

You can represent different types of recursion in the following diagram. This diagram shows the different types of recursion depending on their implementation—in other words, linear, tail, mutual, and so forth—and when it will be performed.

Now you will explore different type of algorithms one by one and take a look at their run time as well as compile time implementations.

3. Linear Recursion

Linear recursion is the simplest form of recursion and perhaps the most commonly used recursion. In this recursion, one function simply calls itself until it reaches the termination condition (also known as base condition); this process is known as winding. After calling the termination condition, the execution of the programs returns to the caller; this is known as unwinding.

A function may perform some additional tasks during winding or unwinding; in the case of a factorial, it will multiply the input number with the return value of the function during the unwinding phase. This process can be demonstrated with the following diagram (shown below) that shows both the winding and unwinding phases of a factorial function using linear recursion.

Mathematically, you can write the factorial function recursively this way; in other words, when the value of “n” is zero, return one and when the value of “n” is greater than zero, call the function recursively with “n-1” and multiply the result with the return value of the recursive function.


int Factorial(int no)
{
// error condition
if (no < 0)
return -1;

// termination condition
if (0 == no)
return 1;

// linear recursive call
return no * Factorial(no – 1);
}

Program 1: Run time example of Linear Recursion

The preceding program is a run time version of linear recursion. Here, you have a termination condition of 0; this program starts doing unwinding when it reaches the termination condition. There is one more error condition in this program to prevent an infinite function call if someone passed a negative number to this function. This function will simply return -1 as an error if the value of the parameter is negative.


template <int No>
struct Factorial
{
// linear recursive call
enum { value = No * Factorial<No – 1>::value };
};

// termination condition
template <>
struct Factorial<0>
{
enum { value = 1 };
};

Program 2: Compile time example of Linear Recursion

This program is a compile time counterpart of Program 1. Here, you use the template instantiation to perform the recursion. You also have a termination condition in the form of template specialization. This is a very simple example of template specialization and does not have a lot of code, but in a few cases, you might have to rewrite all the code in the template specialization class (or structure) too, because you can’t inherit the code from the template class (or structure) to specialize the class (or structure).

Here, you didn’t even introduce the error condition of a negative number because this program wont even compile if someone tries to call this with a negative number. This is one very big advantage of compile time recursion that you even couldn’t compile the infinite calling condition. However, the error message is perhaps not very obvious in that case.

Here is the usage of compile time recursion.


cout << Factorial<6>::value << endl;
cout << Factorial<0>::value << endl;
cout << Factorial<-2>::value << endl;

Here, the compiler will refuse to compile the last statement and give a long, cryptic error message.

More by Author

Must Read