Go to page: 1  2  3  4  5  6  7  Next

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

(Full Size Image)

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;

About the Author
C++ Developer at Bechtel Corporation.

Go to page: 1  2  3  4  5  6  7  Next

Tools:

Add www.codeguru.com to your favorites Add www.codeguru.com to your browser search box IE 7 | Firefox 2.0 | Firefox 1.5.x Receive news via our XML/RSS feed