Recursion Primer Using C++, Part 2

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;

Recursion Primer Using C++, Part 2

2.2. Compile Time Structure Recursion

Here, you will see the Compile time versions of all of these programs. The Compile time versions of these examples are even more fun, because here you are going to create a data structure at compile time—Compile Time Data Structure. Compile Time Data Structure is in fact not a new concept in C++; further information about it can also be found [1][3]. Here is the compile time equivalent of what you already studied in the previous example.

// Termination of Link List
struct End
{
};

// Node of Static Link List
template <int iData, typename Type>
struct Node
{

   enum { value = iData };
   typedef Type Next;
};

Here, you need one more structure to indicate the termination condition of the link list. You also can say it is an end marker. In the run time version, you don't need any such concept because in that case you simply check the value of the next file in the node. If its value is NULL, it means that it is the last node of the link list.

However, in the case of template meta-programming, you have to do template specialization (or partial template specialization) to stop the recursion. You can do template specialization for any specific type or for any specific value. Here, you can't do template specialization on the value, because the second template parameter is type. Therefore, you have to create one new type to stop the recursive instantiation of the template. The name of the end marker can be anything and it can store whatever you want. In the example, it would be sufficient to make one empty structure to create a new type as an end marker.

Now, the fun part begins. Here are a few examples of traversing a static link list at compile time using recursive template instantiation. In the first example, you will calculate the length of the static link list; in the second, you add the items of the static link list; and in the third, you multiply the items in the static link list. These examples are the compile-time version of the same thing you studied in the previous section. Therefore, you can say these examples are "Compile time, Structure, and Tail Recursion."

// Structure to add the items in the Static Link List
template <typename T>
struct Add;

// Partial Template Specialization call recursively to add items
template <int iData, typename Type>
struct Add<Node<iData, Type> >
{
   enum { value = iData + Add<Type>::value };
};

// Template Specialization to terminate recursion
template <>
struct Add<End>
{
   enum { value = 0 };
};

// Structure to calculate the length of Static Link List
template <typename T>
struct Length;

// Partial Template Specialization call recursively calculate
// the length
template <int iData, typename Type>
struct Length<Node<iData, Type> >
{
   enum { value = 1 + Length<Type>::value };
};

// Template Specialization to terminate recursion
template <>
struct Length<End>
{
   enum { value = 0 };
};


// Structure to multiply the items in the Static Link List
template <typename T>
struct Multiply;

// Partial Template Specialization call recursively to
// multiply items
template <int iData, typename Type>
struct Multiply<Node<iData, Type> >
{
   enum { value = iData * Multiply<Type>::value };
};

// Template Specialization to terminate recursion
template <>
struct Multiply<End>
{
   enum { value = 1 };
};

Here is the usage of the static link list.

typedef Node<15, Node<20, Node<35, End> > > staticList;

std::cout << Length<staticList>::value   << std::endl;
std::cout << Add<staticList>::value      << std::endl;
std::cout << Multiply<staticList>::value << std::endl;

2.3. Run Time Generative Recursion

Here is an example of Generative Runtime recursion. Suppose you want to calculate the number of digits in a given number; you can calculate it by dividing the original number by 10 until it becomes less than 10 and count all the divisions. For example, if the given number is 34253, the first time you divide this number by 10 you will get 3425, (Here, you are storing the result in an integer variable; therefore, you don't care about the floating point values.) Subsequently, you will get 342, 34, and 3.

You can implement this problem more than one way; the most obvious ways are looping and recursion. Even in recursion you can use a different recursive technique to do this. Here, you will solve this problem with tail recursion.

// Generative, Runtime, and Tail Recursion
// To calculate the Number of Digits in a given number
int CountDigit(int no, int a = 1)
{
   if (no < 10)
      return a;
   else
      return CountDigit(no / 10, ++a);
}

2.4. Compile Time Generative Recursion

As you saw in the previous article, most of the time when you are discussing recursion you usually also mention their mathematical equation too, but this is not the case in the previous example. There can be several other good mathematical examples to discuss generative and structure recursion with compile time and run time variants. But, there is one very good reason to select that example. This example has more than one termination condition to stop recursion. As you have seen in the run time version of this problem, the termination condition is when the input number is less than 10—no matter whether it is 0, 1, 2, or any other number less than 10.

Here is the first attempt to solve this problem—a naïve approache. Here, you created a specialization class for all the termination conditions.

// Generative, Compile time, and Tail Recursion
// To calculate the Number of Digits in a given number
template <int no, int a>
struct CountDigit
{
   enum { value = CountDigit<no / 10, (a+1)>::value };
};

// Partial Template Specialization for Termination Condition
template <int a>
struct CountDigit<0, a>
{
   enum { value = a };
};


template <int a>
struct CountDigit<1, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<2, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<3, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<4, a>
{
   enum { value = a };
};

template <nt a>
struct CountDigit<5, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<6, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<7, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<8, a>
{
   enum { value = a };
};

template <int a>
struct CountDigit<9, a>
{
   enum { value = a };
};

Here is an example of its usage.

std::cout << CountDigit<1234, 1>::value  << std::endl;
std::cout << CountDigit<8, 1>::value     << std::endl;
std::cout << CountDigit<23, 1>::value    << std::endl;
std::cout << CountDigit<43565, 1>::value << std::endl;
std::cout << CountDigit<123, 1>::value   << std::endl;

There are two major problems with this version. The first one is, of course, that you write almost the same code for every condition. The second one is even more severe. This program doesn't truly reflect the run time counterpart. Here, you assumed that only positive numbers are less than 10 and completely ignore the negative numbers. This program will produce the wrong result if you use this with negative number.

Recursion Primer Using C++, Part 2

This problem is very serious to handle, because all negative numbers are less than 10. To make this program work on all negative numbers, you have to make infinite specialization classes.

Here is the first approach to solve both problems. In the next program, you will use the preprocessor macro to generate the template specialization classes automatically. At the same time, you also try to attack the infinite template specialization classes by restricting it to only 19 cases (9 for positive numbers, 9 for negative numbers, and one for zero). Because you know that if you keep dividing any number (positive or negative) by 10, eventually you will get a single digit number in the range of -9 to 9.

#define COUNTDIGIT_SPECIALIZATION(X) \
template <int a> \
struct CountDigit<X, a> \
{ \
   enum { value = a }; \
};

// Generative, Compile time, and Tail Recursion
// To calculate the Number of Digits in a given number
template <int no, int a>
struct CountDigit
{
   enum { value = CountDigit<no / 10, (a+1)>::value };
};

COUNTDIGIT_SPECIALIZATION(0)
COUNTDIGIT_SPECIALIZATION(1)
COUNTDIGIT_SPECIALIZATION(2)
COUNTDIGIT_SPECIALIZATION(3)
COUNTDIGIT_SPECIALIZATION(4)
COUNTDIGIT_SPECIALIZATION(5)
COUNTDIGIT_SPECIALIZATION(6)
COUNTDIGIT_SPECIALIZATION(7)
COUNTDIGIT_SPECIALIZATION(8)
COUNTDIGIT_SPECIALIZATION(9)
COUNTDIGIT_SPECIALIZATION(-1)
COUNTDIGIT_SPECIALIZATION(-2)
COUNTDIGIT_SPECIALIZATION(-3)
COUNTDIGIT_SPECIALIZATION(-4)
COUNTDIGIT_SPECIALIZATION(-5)
COUNTDIGIT_SPECIALIZATION(-6)
COUNTDIGIT_SPECIALIZATION(-7)
COUNTDIGIT_SPECIALIZATION(-8)
COUNTDIGIT_SPECIALIZATION(-9)

Here is an example of the second version of the compile time generative recursion.

std::cout << CountDigit<1234, 1>::value  << std::endl;
std::cout << CountDigit<-8, 1>::value    << std::endl;
std::cout << CountDigit<-23, 1>::value   << std::endl;
std::cout << CountDigit<43565, 1>::value << std::endl;
std::cout << CountDigit<123, 1>::value   << std::endl;

This program still has one problem. In the preceding problem, you came across with a problem with 19 termination conditions, but what will be the situation when your termination condition will be less than 1000 or 100,000? You are not going to write the specialization class 100,000 times, but you still have to use the preprocessor macro 100,000 times. In other words, indirectly you are going to introduce that much template specialization with the help of a preprocessor.

In the next attempt, you are going to solve this problem by introducing one more template class and one more non type template parameter. Now, you are going to introduce one more template class to check the condition that can be even more complex than the example.

There are two main advantage of this technique: First, you are no longer using a preprocessor macro to generate lots of template specialization classes. Second, you can handle almost any termination condition without creating tons of new specialization classes.

// Helper template to see whether the given number is a single digit
template <int no>
struct IsSingleDigit
{
   enum { value = (no > -10 &amp; no < 10) ? 1 : 0 };
};

// Generative, Compile time, and Tail Recursion
// To calculate the Number of Digits in a given number
template <int no, int a, int isSingleDigit>
struct CountDigit
{
   enum { value = CountDigit<no / 10, (a+1),
      IsSingleDigit<no / 10>::value>::value };
};

// Partial Template Specialization
// to stop recursion when the number has only one digit
template <int no, int a>
struct CountDigit<no, a, 1>
{
   enum { value = a };
};

Here is an example of using the third version of compile time generative recursion.

std::cout << CountDigit<1234, 1,
   IsSingleDigit<1234>::value>::value << std::endl;
std::cout << CountDigit<-8, 1,
   IsSingleDigit<-8>::value>::value << std::endl;
std::cout << CountDigit<-23, 1,
   IsSingleDigit<-23>::value>::value << std::endl;
std::cout << CountDigit<43565, 1,
   IsSingleDigit<43565>::value>::value << std::endl;
std::cout << CountDigit<123, 1,
   IsSingleDigit<123>::value>::value << std::endl;

In the last version of the program, you just did some cosmetic changes to make it easier for the caller to call it by using the default value of the template parameter. You almost always passed one as a second parameter and the return value of IsSingleDigit as a third parameter; therefore, you use this as a default parameter in your CountDigit structure.

// Helper template to see whether the given number is a single digit
template <int no>
struct IsSingleDigit
{
   enum { value = (no > -10 && no < 10) ? 1 : 0 };
};

// Generative, Compile time, and Tail Recursion
// To calculate the Number of Digits in a given number
template <int no,
   int a = 1,
   int isSingleDigit = IsSingleDigit<no>::value>
struct CountDigit
{
   enum { value = CountDigit<no / 10, (a+1),
      IsSingleDigit<no / 10>::value>::value };
};

// Partial Template Specialization
// to stop recursion when number has only one digit
template <int no, int a>
struct CountDigit<no, a, 1>
{
   enum { value = a };
};

Now, the usage of this structure is pretty straightforward and more readable. Here is an example of using the fourth version of compile time generative recursion.

std::cout << CountDigit<1234>::value  << std::endl;
std::cout << CountDigit<-8>::value    << std::endl;
std::cout << CountDigit<-23>::value   << std::endl;
std::cout << CountDigit<43565>::value << std::endl;
std::cout << CountDigit<123>::value   << std::endl;

[Recursion02_2.jpg]

Figure 2: More Recursion Types

In the last section of the first part of this article[5], I discussed template recursion with the run time and compile time components of a program. You made a program to generate the simple class to make an n-dimension array using template recursion. In that program and all of the compile time recursion programs, you used the non-type template argument. There is one very important feature of the template meta-programming with the help of type; when instead of a writing program for one specific type, you can generalized it for any type that qualifies the concept used in the program.

Recursion Primer Using C++, Part 2

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.

3.1. Structured Linear Recursion

A link list, again, is perhaps the most commonly used data structure for linear recursion. You have already studied a link list in the previous section; this time, you are going to print the elements in the link list. You can do the same thing with looping—traverse each elements of the link list until you reach the element with the next address equal to NULL. Here is the simple recursive implementation of printing all the elements of a link list.

// Node for Single Link List
struct Node
{
   int     value;
   Node*   next;
};

// Singly Link List Traversal using Linear Recursion
// Structure Linear Recursion
void PrintNode(Node* pHead)
{
   if (pHead != NULL)
   {
      PrintNode(pHead->next);
      std::cout << pHead->value << std::endl;
   }
   else
      return;
}

3.2. Generative Linear Recursion

If you are supposed to make a function that will create and populate a vector (or any other data structure) with some predefined data, you can solve this either with looping or with recursion. Here is the recursive version of the function.

bool makeVector(std::vector<int>& vec, int low, int high,
   int increment = 1)
{
   if (low > high)
      return false;

   if (low == high)
      return true;
   else
   {
      vec.push_back(low);
      makeVector(vec, low+increment, high, increment);
   }

   return true;
}

In this function, you are inserting the low value in the vector; then, you increment it and then call it recursively until the low value becomes larger than higher value. Here is the usage of this function.

std::vector<int> vec;
makeVector(vec, -5, 10, 2);
std::copy(vec.begin(), vec.end(),
   ostream_iterator<int>(std::cout, "\n"));

This might not be a good and interesting example of generative linear recursion. Look at a variation of the Josephus Problem discussed in the Concrete Mathematics book[4].

"During the Jewish-Roman war, he [Josephus] was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left." [4]

"In our variation, we start with n people numbered 1 to n around a circle, and we eliminate every second remaining person until only one survives" [4].

Here is the mathematical formula to solve this problem.

[Recursion02_3.jpg]

Figure 3: The Josephus Problem

One more reason to select this example was that, from the equation, there isn't any obvious solution for any value of n greater than 1. In other words, you can't see what function would work in the case of J(n). If you look at this closely, these equations just show two special cases: one for even numbers and the other for odd numbers in addition to a termination condition. Here is the simple implementation of the Modified Josephus Problem in C++ using recursion.

// Modified Josephus Problem
// As Described in Concrete Mathematics
int JosephusProblem(int no)
{
   if (1 == no)
      return 1;

   if (no % 2 == 0)
      return 2 * JosephusProblem(no / 2) - 1;
   else
      return 2 * JosephusProblem(no / 2) + 1;
}

4. Tail Recursion

Tail recursion is a specialized form of linear recursion where the recursive function call is usually the last call of the function. This type of recursion usually is more efficient because a smart compiler will convert this recursion automatically into a loop to avoid nested function calls. Because a recursive function call is usually the last statement of a function, there isn't any work done during the unwinding phase; instead, it simply returns the value of the recursive function call. In other words, a recursive function doesn't store any state information and, during the unwinding phase, it just returns the value.

4.1. Structured Tail Recursion

Take another example of the link list. If you want to find the maximum value in the link list, you can do it either with looping or with recursion. Here is an example to find the maximum value in the link list by using tail recursion.

// Find the maximum value of link list using Tail Recursion
int maxValue(Node* pHead, int MaxValue)
{
   if (pHead->next == NULL)
      return MaxValue;
   else
      return maxValue(pHead->next,
         pHead->value > MaxValue ? pHead->value : MaxValue);
}

Here is the simple usage of this function.

Node* pHead = NULL;

AddNode(&pHead, 15);
AddNode(&pHead, 20);
AddNode(&pHead, 65);
AddNode(&pHead, 25);
AddNode(&pHead, 55);
AddNode(&pHead, 40);

if (pHead != NULL)
{
   std::cout << maxValue(pHead, pHead->value) << std::endl;
}

Here, it doesn't matter whether the link list is valid or not before calling the function because you are passing the value of the first node of the link list as a parameter of the function.

4.2. Generative Tail Recursion

If you want to reverse the number, again you can perform it in different ways. Here is the simple tail recursion version of it.

// Reverse the given number using Tail Recursion
int reverseNumber(int n, int r = 0)
{
   if (n == 0)
      return r;
   else
      return reverseNumber(n/10, (r*10)+(n%10));
}

This function calls itself again and again recursively and passes the input parameter after dividing by 10 until it is equal to 0. At the same time, this function creates a reverse number and passes it as a second parameter of itself; during the unwinding phase, it just returns the number as it is.

Recursion Primer Using C++, Part 2

5. Mutual Recursion

Mutual recursion is also known as indirect recursion. In this type of recursion, two or more than two functions call each other in a circular way. This is the only way of doing recursion if the programming language doesn't allow calling a function recursively. The termination condition in this recursion can be in one or all functions.

5.1. Structure Mutual Recursion

Take a look at the problem to check that the given string is a palindrome or not. A palindrome string is a string that can be the same no matter it's read from the left or right, such as "Hannah,", "Tenet," "Civic," "Madam," and so forth. By definition, a one-letter word is also a palindrome; therefore, this function returns true if the length of given string is only one. This function calls another helper function named "helperPlaindrome", which checks the first and last letters of the string and calls isPlaindrome again.

Here is the simple implementation of checking whether a string is a palindrome or not by using Mutual recursion.

// Structure Mutual Recursion
bool isPlaindrome(const std::string& str);
bool helperPlaindrome(const std::string& str);

bool isPlaindrome(const std::string& str)
{
   // base condition
   if (1 == str.length())
      return true;

   // Call the helper function
   return helperPlaindrome(str);
}

bool helperPlaindrome(const std::string& str)
{
   // call function isPlandrome
   // after checking first and last character in string
   if (str.length())
      return str.at(0) == str.at(str.length() - 1)
         && isPlaindrome(str.substr(1, str.length() - 2));
   else
      return true;
}

5.2. Generative Mutual Recursion

In the previous article, you have already seen two examples of mutual recursion. A few more interesting examples of mutual recursion are defined in this paper [2]. You have already learned abut the Fibonacci numbers. The actual problem of Fibonacci numbers is defined as a pair of rabbits and you are supposed to calculate the total number of rabbits after n months. These are the conditions defined in the problem.

During the first month, there is only one pair of rabbits; it's supposed the take one month to produce one more pair of babies who never die. In addition, they always produce a pair of one male and one female rabbit. If you count the total number of pairs every month, these are Fibonacci numbers.

Instead of calculating the number of pairs every month, if we want to calculate the number of Adult pairs (mature paired) and number of Baby pairs, you can calculate it with the following formulae.

[Recursion02_4.jpg]

Figure 4: Equation of Baby Rabbit Pairs

[Recursion02_5.jpg]

Figure 5: Equation of Adult Rabbit Pairs

This is a type of mutual recursion. In this example, the "Baby" function calls the "Adult" function and vice versa. Here is the simple implementation of this problem.

int BabyPair(int no);
int AdultPair(int no);

int BabyPair(int no)
{
   if (no == 1)
      return 1;
   else
      return AdultPair(no - 1);
}

int AdultPair(int no)
{
   if (no == 1)
      return 0;
   else
      return AdultPair(no - 1) + BabyPair(no - 1);
}

6. Binary Recursion

In binary recursion, the recursive function call itself twice, not once. This type of recursion is very useful with some data structures, like traversing a tree in prefix postfix or infix order, generating Fibonacci numbers, and so forth.

Binary recursion is a specific form of exponential recursion, where one function calls the recursive function more than once (in the case of binary two). In other words, recursive functions call exponentially in this type of recursion.

6.1. Structure Binary Recursion

Binary Tree is a typical example if Binary Recursion. In a Binary tree, every node has two child nodes and every child node may contain two children. Recursion is a natural choice here, because of the recursive nature of the data structure. Here is the simple code to add items in Binary tree and display it.

// Node for Binary Tree
struct TreeNode
{
   int         iData;
   TreeNode*   pLeft;
   TreeNode*   pRight;
};


// Add Items in Binary Tree
void AddItem(TreeNode** pRoot, int iData)
{
   if (*pRoot == NULL)
   {
      (*pRoot) = new TreeNode();
      (*pRoot)->iData = iData;
      (*pRoot)->pLeft = NULL;
      (*pRoot)->pRight = NULL;
   }
   else
   {
      if (iData < (*pRoot)->iData)
         AddItem(&(*pRoot)->pLeft, iData);
      else if (iData > (*pRoot)->iData)
         AddItem(&(*pRoot)->pRight, iData);
   }
}

// Traversing Binary Tree
// Structure Binary Recursion 
void PrintTree(TreeNode* pRoot)
{
   if (pRoot == NULL)
      return;

   PrintTree(pRoot->pLeft);
   std::cout << pRoot->iData << std::endl;
   PrintTree(pRoot->pRight);
}

At first, it looks like AddItem is using Binary recursion, because it calls itself twice, but that is not a case. For any given value, the AddItem function calls itself only once, either to insert in items in the right child or in the left child. PrintTree is a true Binary recursive function, because it calls itself twice for every node, to traverse both left and right children.

As you have already learned, Binary Recursion is just a special case of Exponential Recursion, because in Exponential recursion a recursive function may call itself more than twice. Its example may be a Generalized Tree, not a Binary Tree, where any node of a Tree may contain any number of children. In real life, you can see this as a directory structure of your operating system. Here is the simplest implementation of a Generalized Tree.

// Generalized Tree
struct GeneralizedTreeNode
{
   int iData;
   std::vector<GeneralizedTreeNode*> vecChildern;
};

Recursion Primer Using C++, Part 2

6.2. Generative Binary Recursion

When you consider the problem subdivided into sub problems, Binary Search would be a simple and natural example. In Binary search, you break out a sorted vector into two for each comparison. Here is the simple implementation of a Binary Search.

// Generative Binary Recursion 
int BinarySearch(std::vector<int> vec, int first, int last,
   int val)
{
   if (0 == vec.size())
      return -1;

   if (first > last)
      return -1;
   else
   {
      int mid = (first + last)/2;

      if (vec.at(mid) == val)
         return mid;

      else if (val < vec.at(mid))
         return BinarySearch(vec, first, mid-1, val);

      else
         return BinarySearch(vec, mid+1, last, val);
   }
}

This function is similar to the AddItem function of the BinaryTree. Although there are two recursive calls of BinarySearch, but for any given value there will be only one call. This program is not a true Binary Recursion, because the recursive function doesn't call itself more than once during any call.

Take a look at the example of a merge sort. In a merge sort, you subdivide your array (or vector) into two pieces and keep doing this until there is only one element left in the sub array, and then you merge all the sub arrays together. The splitting piece of this program is quite straightforward and the real fun part is in the mergeVectors function. You can implement the mergeVectors function in two ways. Either you can create a new temporary vector and insert elements in it, or you simply swap the values of existing vectors. In this program, you use the second approach—swap the values of an existing vector rather than create a new one.

// Function to merge two lists
// In this function we are just swaping the values of two vectors
// using nested loop, without creating any new temporary vector
void mergeVectors(std::vector<int>::iterator iStart,
                  std::vector<int>::iterator iMid,
                  std::vector<int>::iterator iEnd)
{
   // Traverse through the first list
   for (std::vector<int>::iterator iter_ = iStart;
      iter_ != iMid;
      ++iter_)
   {
      // if Current element of First list
      // is greater than first element of second list
      // We do not check elements in the first list
      // because both list should already sorted
      if (*iter_ > *iMid)
      {
         // Store the current value in temporary variable
         int iTemp = *iter_;
         *iter_ = *iMid;

         // Store the first position in temporary locaiton
         std::vector<int>::iterator iTempIter = iMid;

         // Move the all the elements of the list to left
         // which are greater than current value
         // to make room for currnet value to insert at the
         // first place of the second list
         while (iTempIter + 1 != iEnd && *(iTempIter + 1) < iTemp)
         {
            std::swap(*iTempIter, *(iTempIter + 1));
            ++iTempIter;
         }

         // Now we have moved all the elements to the next place
         // therefore we can copy the current element
         *iTempIter = iTemp;
      }
   }
}

// Recursive function call itself recursively
void mergeSort(std::vector<int>::iterator iStart,
               std::vector<int>::iterator iEnd)
{
   size_t iSize = iEnd - iStart;
   if (iSize <= 1)
      return;

   std::vector<int>::iterator iMid = iStart + (iSize / 2);

   // Call itself twice example of Binary Recursion
   mergeSort(iStart, iMid);
   mergeSort(iMid, iEnd);

   mergeVectors(iStart, iMid, iEnd);
}

7. Nested Recursion

This is a special type of recursion when the recursive call is nested. In all of the above recursions, you can replace them with either simple looping or a loop with a stack, but this type of recursion cannot be easily replaced by a simple loop. In this type of recursion, every recursive function calls another function that is also a recursive function. The nested recursive function can be the function itself or it can be another function altogether.

7.1. Structure Nested Recursion

A Nested Link List can be a good example of Structured Nested Recursion. In a simple link list, every node of the Link List simply contains data as well as the address of the next node. In the case of a nested link list, every node of a link list contains two addresses. The first address is just like the simple link list; it contains the address of the next node in the link list, but the second node is an address of one more link list.

In other words, every node can contain the address of one more link list. Now the question is, "What might be the advantage of such a complex data structure, when you can do the same thing with two dimensional arrays?" The main problem with two-dimensional arrays is that every dimension should have the same length, just like a Matrix. You can't make a 2D array with every row containing a different number of elements.

The solution of this problem is the Array of pointer, where every element of the array stores the address of another single-dimensional array. It will solve your 2D array with a variable number of elements in the row as shown in Figure 6.

[Recursion02_6.jpg]

Figure 6: Array of Pointers

But, you still have two problems in it. First, because the array is a fixed length and if you want to increase the size of any array, you have to reallocate it in memory, copy all the elements from previous location to new location, and de-allocate the previous memory location. This, of course, is a very expensive solution both in terms of time as well as memory.

Link List came into the picture to solve exactly the same problem. If you store that information in Link List instead of an array, you easily can grow it dynamically it without performing all the expensive steps.

Here, you have two different types of Nodes. A Node is same as you studied earlier in the case of a Simple Link List. NestedNode has two pointers: one to store the address of next node of same type to create a link list of NestedNode type and other to store the header address of the nested link list.

[Recursion02_7.jpg]

Figure 7: Nested Link List

Recursion Primer Using C++, Part 2

Here is the simple implementation of both types of nodes in a nested link list.

// Node for Inner Link List
struct Node
{
   int     iData;
   Node*   pNextNode;

   Node()
   {
      iData = 0;
      pNextNode = NULL;
   }
};

// Node for Nested Link List
struct NestedNode
{
   int           iData;
   Node*         pHead;
   NestedNode*   pNextList;

   NestedNode()
   {
      iData = 0;
      pHead = NULL;
      pNextList = NULL;
   }
};

Here are the functions to add items in the Nested Link List and the Nested Link List itself.

// Add element in the outer link list
NestedNode* AddNestedList(NestedNode* pHead, int iData)
{
   if (pHead == NULL)
      return NULL;

   if (pHead->pNextList == NULL)
   {
      pHead->pNextList = new NestedNode();
      pHead->iData = iData;
      return pHead;
   }
   else
   {
      NestedNode* pTemp = pHead->pNextList;

      while (pTemp != NULL)
      {
         pTemp = pTemp->pNextList;
      }

      pTemp = new NestedNode();
      pTemp->iData = iData;
      pTemp->pNextList = pHead;
      pHead = pTemp;
      return pHead;
   }
}

// Add element in the inner link list
void AddNestedItem(Node** pHead, int iData)
{
   if (*pHead == NULL)
   {
      *pHead = new Node();
      (*pHead)->iData = iData;
   }
   else
   {
      Node* pTemp = (*pHead)->pNextNode;

      while (pTemp != NULL)
      {
         pTemp = pTemp->pNextNode;
      }

      pTemp = new Node();
      pTemp->iData = iData;
      pTemp->pNextNode = *pHead;
      *pHead = pTemp;
   }
}

Here is the usage of these functions to create a Nested Link List.

// Header of Nested Link List
NestedNode* pNested = new NestedNode();

// First Nested Link List store items multiple of 2
pNested = AddNestedList(pNested, 2);
AddNestedItem(&pNested->pHead,   4);
AddNestedItem(&pNested->pHead,  14);
AddNestedItem(&pNested->pHead,  20);
AddNestedItem(&pNested->pHead,  36);

// Second Nested Link List store items multiple of 3
pNested = AddNestedList(pNested, 3);
AddNestedItem(&pNested->pHead,   9);
AddNestedItem(&pNested->pHead,  21);
AddNestedItem(&pNested->pHead,  27);

// Third Nested Link List store items multiple of 5
pNested = AddNestedList(pNested, 5);
AddNestedItem(&pNested->pHead,  25);
AddNestedItem(&pNested->pHead,  45);
AddNestedItem(&pNested->pHead,  50);
AddNestedItem(&pNested->pHead,  70);
AddNestedItem(&pNested->pHead,  85);
AddNestedItem(&pNested->pHead,  95);

And here is the function to print a Nested Link List.

// Print the inner link list
void PrintNestedList(Node* pHead)
{
   if (pHead != NULL)
   {
      std::cout << " -> " << pHead->iData << std::endl;
      PrintNestedList(pHead->pNextNode);
   }
   else
      return;
}

// Print the outer link list
void TraverseNode(NestedNode* pHead)
{
   if (pHead == NULL)
      return;
   else
   {
      std::cout << pHead->iData << std::endl;
      PrintNestedList(pHead->pHead);
      TraverseNode(pHead->pNextList);
   }
}

Here is the example of calling this function.

// Traverse Nested Link Recursively
// Every items itself is Link List
// Traverse that Link List Recursively too
// to print all items in Nested Link List
// Recursive function call another recursive function
TraverseNode(pNested);

7.2. Generative Nested Recursion

In the previous article, you studied the Ackermann function as an example of nested recursion. Here, instead of repeating the same example, you will study one more nested recursive function, named the McCarthy function, also known as the McCarthy 91 function.

Mathematically, the McCarthy function can be defined as shown i Figure 8:

[Recursion02_8.jpg]

Figure 8: McCarthy Function

// Generative Nested Recursion
int McCarthy(int no)
{
   if (no > 100)
      return no - 10;
   else
      return McCarthy(McCarthy(no + 11));
}

8. References

  1. Modern C++ Design Generic Programming: Andrei Alexandrescu
  2. A Gentle Introduction to Mutual Recursion: Manuel Rubio-Sanchez, Jaime Urquiza-Fuentes, Cristobal Pareja-Flores. Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain.
  3. Static Data Structure: Michael C. Burton, William G. McCulloch, Gary A. Huber
  4. Concrete Mathematics 2nd edition: Ronald L. Graham, Donald E Knuth, Oren Patashnik
  5. Recursion Primer Using C++: Part 1: Zeeshan Amjad. http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_01.aspx
    http://www.codeguru.com/cpp/cpp/algorithms/math/article.php/c15111/


About the Author

Zeeshan Amjad

C++ Developer at Bechtel Corporation. zamjad.wordpress.com

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • Targeted attacks and advanced threats are customized to infiltrate your unique IT infrastructure, evade conventional defenses, and remain hidden while stealing your corporate data. To detect these criminal intrusions, analysts and security experts agree that organizations should deploy advanced threat protection as part of an expanded security monitoring strategy. For this comparative analysis of breach detection systems, product analysis reports and comparative analysis reports are used to create the security …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds