Recursion Primer Using C++, Part 2
1. Introduction
In the first part of this article, “Recursion Primer Using C++, Part 1,” you studied different types of recursion and their implementation using C++ [5]. You studied recursion from two different dimensions: first, either it is performed at compile time or at run time; second, you learned about five different types of recursion. Now, you are going to study recursion again, this time with one more dimension.
2. Recursion Types
Recursion also can be classified into two types: Structure Recursion and Generative Recursion. The main difference between these are that Generative recursion usually decomposes the original problem into sub problems and solves it. For example, to calculate the factorial of a given number, you calculate the factorial of a number one less than the given number and keep doing this until you reach the termination condition. In the case of a binary search, you divide the given array into two pieces and run the binary search on that. In this case, you eliminate half of the elements during every recursive call until you either find the required element or reach a point where you have only one element left. Now, if that element is required, you found it at after Log2 (n) comparison (in other words, the worst case); where “n” is the total number of elements in an array.
On the other hand, Structure recursion usually performs data rather than decomposing the problem into smaller pieces. You can store data in recursive structures, such as a Binary Tree; in that case, it would be natural to use recursion to perform an operation on it. Structure recursion is not only limited to recursive data structure, but it would be very handy in some linear structures such as Link List.
In the previous article [5], you studied two dimensions of recursion: recursion types such as linear, tail, binary, and so forth; and whether it happens at compile time or at run time. Here, you added one more dimension in it—structure recursion and generative recursion—and now you are going to study that.
First, you will study the compile time and run time variants of structure and generative programming. For the compile time version, you are again going to study template meta0programming. In fact, you have already studied the generative compile time recursion in the previous article. Almost all of the template meta-programming examples given in the previous article are also examples of generative recursion.
You can define this relationship with this simple block diagrams. Figure 1 is very similar to the one you have already seen in the previous article.
Figure 1: Recursion Types
The syntax of template meta-programming is still most confusing to even an experienced C++ developer until he/she got his/her hands dirty with it a little bit. Therefore, I decided to use the same example for compile time and run time recursion for easy comparison between these two.
2.1. Run Time Structure Recursion
I decided to select the link list as an example to discuss run time and compile time structure recursion. The main reason for this is that it is very easy to implement and understand.
Here is a simple structure of a link list node. Although this node contains only one data element, it can be easily extended to store as much information as you want.
// Node for Single Link List
struct Node
{
int value;
Node* next;
};
Before you actually start playing with the link list, it would be helpful to make a function to add items in the link list. Here is one simple function to add the values in the link list. This implementation is not the world’s best implementation of adding values in the link list (what will be the case when there isn’t enough memory to allocate a new node?), but for your purposes this can be a good candidate of proof of concept.
// Add values in a Single Link List
void AddNode(Node** pHead, int value)
{
// insert first time
if (*pHead == NULL)
{
*pHead = new Node();
(*pHead)->value = value;
(*pHead)->next = NULL;
}
// insert after that
else
{
Node* pTemp = *pHead;// traverse until end of list
while (pTemp != NULL)
{
pTemp = pTemp->next;
}pTemp = new Node();
pTemp->value = value;
pTemp->next = *pHead;
*pHead = pTemp;
}
}
Now, you have enough tools to start playing with it. Here are a few examples of traversing a Single Link List recursively. If you look at it closely, you also can notice that all of these examples are also types of tail recursion, which you already studied in the previous article. You can even call these examples “Run time time, Structure, and Tail Recursion.”
// Count the elements of the link list
int Count(Node* pHead, int iCount = 0)
{
if (pHead == NULL)
return iCount;
else
return Count(pHead->next, ++iCount);
}// Add the values of the link list
int Add(Node* pHead, int iSum = 0)
{
if (pHead == NULL)
return iSum;
else
return Add(pHead->next, pHead->value + iSum);
}// Multiply the values of the link list
int Multiply(Node* pHead, int iMultiply = 1)
{
if (pHead == NULL)
return iMultiply;
else
return Multiply(pHead->next, pHead->value * iMultiply);
}
Here is the usage of these functions:
Node* pHead = NULL;AddNode(&pHead, 15);
AddNode(&pHead, 20);
AddNode(&pHead, 35);std::cout << Count(pHead) << std::endl;
std::cout << Add(pHead) << std::endl;
std::cout << Multiply(pHead) << std::endl;
