1. Introduction

In first two parts of this article, we discuss recursion from a different dimension. In Recursion Primer Using C++, Part 1 we discussed how to implement the five different types of recursion at run time and compile time. Recursion Primer Using C++, Part 2 discussed the same five different types of recursion from another dimension, i.e. generative recursion and structure recursion. This article will combine all of the dimensions together, i.e. compile time/runtime and structure/generative with five different types of recursion.

2. Types of Recursion

2.1. Recursion Types on the Basis of Execution

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.

2.2. Recursion Types on the Basis of Data and Problem

Recursion can also be classified by Structure Recursion and Generative Recursion. The main difference between these are, Generative recursion usually decomposes the original problem into sub problem and solves it. For example to calculate the factorial of a given number, we calculate the factorial of a number one less than the given number and keep doing this until we reach the termination condition. In the case of a binary search, we divide the given array into 2 pieces and run the binary search on that. In this case, we eliminate half of the elements during every recursive call until we either found the required element or reach a point where we have only one element left. Now if that element is required then we found it at after Log2 (n) comparison (i.e. 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. We can store data in recursive structures such as Binary Tree and 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.

2.3. Recursion Types on the Basis of Algorithm

The other way to see the recursion is how the recursive algorithm is implemented. Recursive algorithm can be implemented in more than one way such as linear, tail, mutual, binary or nested recursion.

In this article we are going to study recursion types with respect to all the dimensions. It means we are going to study 20 different types of recursion. Also note that we didn't even include the template recursion, which we discussed in Recursion Primer Using C++, Part 1. We can display these three dimensions of the recursion types with this simple block diagram.

Figure 1: Dimensions of Recursion

Because this is a three dimensional type of recursion, we can't simply represent this with one table. One possible table representation is to fix one type of recursion in one table and display all other possibilities. One possible break down is break it by compile time and runtime. This is a quite logical break down because compile time recursion is not possible in all programming languages. If someone is using other than C++, the compile time table can be ignored.

Here is a table to represent different types of run time recursive algorithm.

Figure 2: Runtime Recursive Algorithms

Similarly, here is a table to represent different types of compile time recursive algorithm. These types of recursive algorithms are very specific to C++, because not every language supports compile-time recursion or template meta programming.

Figure 3: Compiletime Recursive Algorithms

This diagram shows the 20 different types of algorithms in a little bit more detail in the form of blocks.

Figure 4: Types of Recursion

7. Nested Recursion

This is a special type of recursion when the recursive call is nested. All of the above recursion we can replace them with either simple looping or loop with stack, but this type of recursion cannot be easily replaced by 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. Runtime Structure Nested Recursion

Nested Link List can be a good example of Structured Nested Recursion. In 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 nested link list, every node of a link list contains two addresses. The first address is just like a simple link list contains the address of 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 we 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 Matrix. We can't make a 2D array with every row containing different number of elements.

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

Here is a simple example of both types of nodes and nested recursive implementation to display the values of the nested link list. Here we have recursive TraverseNode method, which internally calls PrintNestedList method that is also a recursive function. TraverseNode prints the outer link list and PrintNestedList, as the name suggests, prints the values of 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; 
        } 
};
// 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 a simple usage of 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. Compile Time Structure Nested Recursion

In a similar way we can create a nested link list at compile time. Here we defined two node types, just like the runtime version. In addition we have to define two different end markers, one for link list and the other for nested link list name End and NestedEnd respectively.

// Termination of Link List 
struct End 
{ 
};
 
// Node of Static Link List 
template <int iData, typename Type> 
struct Node 
{ 
        enum { value = iData }; 
        typedef Type Next; 
};
 
// Termination of Nested Link List
struct NestedEnd
{
};
 
// Node of Nested Link List
template <int iData, typename NestedType, typename Type>
struct NestedNode
{
        enum { value = iData };
        typedef NestedType     NestedList;
        typedef Type           Next;
};

Instead of printing the value of nested link list here we are going to count the values in link list and nested link list. Here Count is a structure that recursively instantiates itself as well as Length structure too. Length structure also instantiates itself to calculate the length of nested link list.

// Structure to calculate the length of Static Link List 
template <typename T> 
struct Length; 
 
// Partial Template Specialization call recursiveely 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 calculate the number of elements in Nested Static Link List 
template <typename T> 
struct Count; 
 
// Partial Template Specialization call recursiveely calculate the length 
template <int iData, typename NestedType, typename Type> 
struct Count<NestedNode<iData, NestedType, Type> > 
{ 
        enum { value = 1 + Count<Type>::value + Length<NestedType>::value }; 
}; 
 
template <>
struct Count<NestedEnd>
{
        enum { value = 0 };
};

Here is simple usage of these structures.

// Nested Link List
// first nested link list contains elements multiple of 5
// second nested link list contains natural numbers
// third nested link list contains prime number
typedef NestedNode<100, Node<5, Node<10, Node<15, End> > >, 
               NestedNode<200, Node<1, Node<2, Node<3, Node<4, Node<5, Node<6, End> > > > > >, 
               NestedNode<300, Node<2, Node<3, Node<5, Node<7, Node<11, Node<13, Node<17, End> > > > > > >, 
                       NestedEnd> > > nestedList;
 
std::cout << Count<nestedList>::value << std::endl;

7.3. Runtime Generative Nested Recursion

McCarthy function, also known as McCarthy 91 function, is a nested recursive function defined by John McCarthy. This function is proposed as a test case for formal verification of the system. This is also known as McCarthy 91 function because for every value less than 100 this function returns 91.

Here is a mathematical formula of this function.

Figure 10: McCarthy Function

Here is simple implementation of this function.

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

Here is simple usage of this function.

std::cout << McCarthy(25) << std::endl;

7.4. Compile Time Generative Nested Recursion

One more example of a nested recursive function is Ackermann function. This function explodes very rapidly; therefore it is usually used to check the compiler's ability to optimize recursion. Here is mathematical formula for Ackermann function.

Figure 11: Ackermann Function

This is simple compile time implementation of this nested function.

template <int m, int n> 
struct Ackermann 
{ 
        // nested recursive call 
        enum { value = Ackermann<m-1, Ackermann<m, n-1>::value>::value }; 
}; 
 
template <int m> struct Ackermann<m, 0> 
{ 
        // linear recursive call 
        enum { value = Ackermann<m-1, 1>::value }; 
}; 
 
// termination condition 
template <int n> 
struct Ackermann<0, n> 
{ 
        enum { value = n + 1 }; 
};

Here is a usage of this function.

std::cout << Ackermann<2, 3>::value << std::endl;

8. References

1. 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.
2. Concrete Mathematics 2nd edition
   Ronald L. Graham, Donald E Knuth, Oren Patashnik
3. 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/
4. Recursion Primer Using C++: Part 2
   Zeeshan Amjad
   http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_02.aspx
   http://www.codeguru.com/cpp/cpp/algorithms/math/print.php/c15693__4/

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 program returns to the caller; this is known as unwinding.

3.1. Runtime Structure Linear Recursion

Single link list is perhaps the most commonly used and simple to implement data structure for linear recursion. We can implement the link list algorithms both iteratively or recursively. Here is the simple recursive implementation of printing all the elements of a single link list recursively.

// 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. Compile Time Structure Linear Recursion

We can implement the compile time version of the link list too, with the help of template meta- programming. Here is a simple code to create a node of compile time single link list.

// 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 we need the first empty structure to terminate the recursion and use it as a base class. The whole purpose of this empty structure is to introduce one more type that does nothing, and use this in a template specialization or partial template specialization to terminate the compile time recursion. Here is an example of creating the compile time single link list.

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

In Compile time world, we can't perform the looping. The only way to simulate it is using compile time recursion. Here are few algorithms on compile time single link list using compile time recursion.

// Structure to calculate the length of Static Link List 
template <typename T> 
struct Length; 
 
// Partial Template Specialization call recursiveely calculate the length 
template <int iData, typename Type> 
struct Length<Node<iData, Type> > 
{ 
        enum { value = Length<Type>::value + 1 }; 
}; 
 
// Template Specialization to terminate recursion 
template <> struct Length<End> 
{ 
        enum { value = 0 }; 
};
 
// Structure to add the items in 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 = Add<Type>::value + iData }; 
};
 
// Template Specialization to terminate recursion 
template <> 
struct Add<End> 
{ 
        enum { value = 0 }; 
};
 
// Structure to multiply the items in 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 =  Multiply<Type>::value * iData}; 
}; 
 
// Template Specialization to terminate recursion 
template <> struct Multiply<End> 
{ 
        enum { value = 1 }; 
};

And here is the usage of it.

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

3.3. Runtime Generative Linear Recursion

If we are supposed to make a function that will create and populate a vector (or any other data structure) with some predefined data then we 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 we are inserting the low value in the vector then incrementing it and then calling it recursively until the low value becomes larger than the higher value. Here is the usage of this function.

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

3.4. Compile Time Generative Linear Recursion

Perhaps the simplest and the most famous example of generative linear recursion is calculating the factorial. While calculating the factorial, we continuously divide the problem into sub problem. Here is an example of compile time generative linear recursion.

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

Here is the usage of this.

std::cout << Factorial<6>::value << std::endl;

Let's take a look at variation of Josephus problem discussed in Concrete Math [2].

"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."[2]

"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"[2].

Here is the mathematical formula to solve this problem.

[Recursion_03_05.jpg]
Figure 5: Josephus Problem

Here is compile time generative liner recursion function to solve this problem.

// Josephus Problem
template <int No> struct JosephusProblem
{
        enum { value = No % 2 == 0 ? 2 * JosephusProblem<No / 2>::value - 1 : 
               2 * JosephusProblem<No / 2>::value + 1 };
};
 
// termination condition 
template <> struct JosephusProblem<0>
{
        enum { value = 1 };
};

Here is the usage of it.

        std::cout << JosephusProblem<5>::value << std::endl;
        std::cout << JosephusProblem<8>::value << std::endl;
        std::cout << JosephusProblem<4>::value << std::endl;

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 is usually more efficient because smart compiler will automatically convert this recursion into a loop to avoid nested function calls. Because recursive function call is usually the last statement of a function there isn't any work done during the unwinding phase, instead of this they simply return the value of recursive function call. In other words recursive function doesn't store any state information and during the unwinding phase just returns the value.

4.1. Runtime Structure Tail Recursion

Let's take a look at the example of single link list again. If we want to find the maximum value in the link list we can do it with either looping or with recursion. Here is an example to find the maximum value in the link list using tail recursion.

// Node for Single Link List 
struct Node 
{ 
        int value; 
        Node* next; 
};
 
void AddItem(Node** pHead, int iData)
{
        if (*pHead == NULL)
        {
               (*pHead) = new Node();
               (*pHead)->value = iData;
               (*pHead)->next = NULL;
        }
        else
        {
               Node* pTemp = *pHead;
 
               while (pTemp->next != NULL)
               {
                       pTemp = pTemp->next;
               }
 
               Node* newNode = new Node();
               newNode->value = iData;
               newNode->next = NULL;
 
               pTemp->next = newNode;
        }
}
// 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;
 
        AddItem(&pHead, 8);
        AddItem(&pHead, 20);
        AddItem(&pHead, 12);
        AddItem(&pHead, 22);
        AddItem(&pHead, 5);
 
        std::cout << maxValue(pHead, 0) << std::endl;

4.2. Compile Time Structure Tail Recursion

We can do the same thing at compile time. First we are going to define some structure to create a compile time link list. Here is a simple code to create a node of compile time single link list.

// Termination of Link List 
struct End 
{ 
};
 
// Node of Static Link List 
template  
struct Node 
{ 
        enum { value = iData }; 
        typedef Type Next; 
};

Now we are going to add all of the values of all elements of the link list. In compile time, the only way to traverse the link list is using recursion, but here we are using Tail recursion to traverse the link list and add the value of all data items.

// Structure to add the items in 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 }; 
};

Here is a simple usage of this

       typedef Node<15, Node<20, Node<35, End> > > staticList; 
        
        std::cout << Add<staticList>::value << std::endl; 

4.3. Runtime Generative Tail Recursion

If we want to reverse the number then again we can perform it with 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 16 passed it as a second parameter of itself and during the unwinding phase just return the number as it is. Here is simple usage of it.

std::cout << reverseNumber(2468) << std::endl;
std::cout << reverseNumber(-1357) << std::endl;

4.4. Compile Time Generative Tail Recursion

This is a modified version of the linear recursion program. Here we perform all the calculation before calling the recursive function, and simply return the value whatever we got from the recursive function.

template <int No, int a>
struct Factorial
{
        // tail recursive call
        enum { value = Factorial<No - 1, No * a>::value };
};
 
// termination condition
template <int a>
struct Factorial<0, a>
{
        enum { value = a };
};

Here is simple usage of this.

std::cout << Factorial<6, 1>::value << std::endl;

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 function recursively. Termination condition in this recursion can be in one or all functions.

5.1. Runtime Structure Mutual Recursion

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

Here is the simple implementation of checking if a string is palindrome or not using 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; 
}

Here is a simple usage of this function

std::cout << isPlaindrome("MADAM") << std::endl;

5.2. Compile Time Structure Mutual Recursion

We are again going to create a compile time link list to write a structure mutual recursion function. This method is very similar to the compile time structure trail recursion function. The only difference is that now we are creating two functions (in compile time world structures) to call each other mutually. We have one function (structure in this case) named Add1, which internally calls Add2; similarly Add2 internally calls Add1 until anyone of them reach the end of link list. Here is a simple implementation of these two mutually recursive functions (structures).

// Structure to add the items in Static Link List 
template <typename T>
struct Add1;
 
// Structure to add the items in Static Link List 
template <typename T>
struct Add2;
 
// Partial Template Specialization call recursively Add2 to add items 
template <int iData, typename Type>
struct Add1<Node<iData, Type> >
{
        enum { value = Add2<Type>::value + iData };
};
 
// Template Specialization to terminate recursion 
template <> struct Add1<End>
{
        enum { value = 0 };
};
 
// Partial Template Specialization call recursively Add1 to add items 
template <int iData, typename Type>
struct Add2<Node<iData, Type> >
{
        enum { value = Add1<Type>::value + iData };
};
 
// Template Specialization to terminate recursion 
template <> struct Add2<End>
{
        enum { value = 0 };
};

Here is a simple usage of these functions.

        typedef Node<15, Node<20, Node<35, End> > > staticList; 
        
        std::cout << Add1<staticList>::value << std::endl;

5.3. Runtime Generative Mutual Recursion

There are few interesting mutual recursion problems discussed here [1]. We already know about Fibonacci numbers. The actual problem of Fibonacci numbers is defined as a pair of rabbits and we 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 and it is supposed the take one month to produce one more pair of babies and never die. In addition they always produce a pair of one male and one female rabbit. If we count the total number of pairs during every month then these are Fibonacci numbers.

Here is mathematical formula to calculate Adult and Baby rabbits [1].

[Recursion_03_06.jpg]
Figure 6: Baby Rabbit

[Recursion_03_07.jpg]
Figure 7: Adult Rabbit

This is a case of mutual recursion because Baby function is calling Adult function and Adult function calls the Baby function. Here is simple program to implement these.

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);
}

Here is a simple usage of these functions.

std::cout << "Adult Pair at 10th generation: " << AdultPair(10) << std::endl;
std::cout << "Baby Pair at 10th generation: " << BabyPair(10) << std::endl;

5.4. Compile Time Generative Mutual Recursion

Let's take a look at another example of mutual recursion. This is known as Male Sequence and Female Sequence. Here is mathematical formula for these.

[Recursion_03_08.gif]
Figure 8: Male Sequence

[Recursion_03_09.gif]
Figure 9: Female Sequence

Here is compile time implementation of this generative mutual recursion.

template <int n> struct MaleSequence 
{ 
        // mutually recursive call 
        enum { value = n - FemaleSequence<MaleSequence<n - 1>::value>::value }; 
}; 
 
// termination condition 
template <> struct MaleSequence<0> 
{ 
        enum { value = 0 }; 
}; 
 
template <int n> struct FemaleSequence 
{ 
        // mutually recursive call 
        enum { value = n - MaleSequence<FemaleSequence<n - 1>::value>::value }; 
}; 
 
// termination condition 
template <> struct FemaleSequence<0> {
        enum { value = 1 };
};

Here is simple usage of this.

std::cout << FemaleSequence<6>::value << std::endl;
std::cout << MaleSequence<6>::value << std::endl;

6. Binary Recursion

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

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

6.1. Runtime Structure Binary Recursion

Binary Tree is a typical example if Binary Recursion. In 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.

// 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); 
        } 
}

Here is simple binary recursive implementation of printing the binary tree. Note for each recursive call we call the same function more than once, in this case twice (because it is binary recursion). If we call the same function more than twice then it is known as exponential recursion.

// 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); 
}

Here is a simple usage of it.

        TreeNode* pRoot = NULL;
 
        AddItem(&pRoot, 10);
        AddItem(&pRoot, 20);
        AddItem(&pRoot, 15);
        AddItem(&pRoot, 12);
        AddItem(&pRoot, 27);
        AddItem(&pRoot, 8);
 
        PrintTree(pRoot);

6.2. Compile Time Structure Binary Recursion

Just like the runtime version, we can create a binary tree at compile time too. Here is a simple node example to create the binary tree. The main difference between this and compile time link list is that here we have two typedef (equivalent to reference in runtime version) for left and right node.

// Node of Static Tree
template <int iData, typename Left, typename Right> 
struct Node 
{ 
        enum { value = iData }; 
        typedef Left left;
        typedef Right right;
};

This simple compile time binary structure recursive function adds all the values in the tree. Note here we call the same function (instantiate structure here) twice to traverse left and right side of the binary tree.

// Structure to add the items in Static Tree 
template <typename T> 
struct Add; 
 
// Partial Template Specialization call recursively to add items values
// Use recursion twice to traverse the tree 
template <int iData, typename Left, typename Right> 
struct Add<Node<iData, Left, Right> > 
{ 
        enum { value = Add<Left>::value + Add<Right>::value + iData }; 
};
 
// Template Specialization to terminate recursion 
template <> 
struct Add<End> 
{ 
        enum { value = 0 }; 
};

Let's do something more interesting rather than just adding the values. Let's try to calculate the height of the binary tree, assuming it is binary search tree. To do this we need some helper function (structure here) for comparison. Here are our helper structures.

// Find the maximum number
template <int u, int v>
struct Maximum 
{
        enum { value = u > v ? u : v };
};
 
// Find the minimum number
template <int u, int v>
struct Minimum
{
        enum { value = u < v ? u : v };
};

Now let's implement the Height method. With the help of helper structures it is very easy to implement and this is also an example of Compile time Structure Binary Recursion.

template <typename T>
struct Height;
 
template <int iData, typename Left, typename Right>
struct Height<Node<iData, Left, Right> >
{
        enum { value = Maximum<Height<Left>::value + 1, Height<Right>::value + 1>::value };
};

Here is a simple usage of it. Note here we first create a binary search tree ourselves, because this compile time tree has very limited functionality and doesn't do this for us.

        typedef Node<100, 
                               Node<50, Node<10, End, End>, Node<75, End, End> >,
                               Node<150, Node<125, End, End>, Node<175, End, End> > > tree1;
 
        typedef Node<100, 
                               Node<50, 
                                      Node<10, 
                                              Node<60, End, End>, 
                                              Node<3, 
                                                     Node<12, End, End>, 
                                                     End> >, 
                                      Node<75, 
                                              End, 
                                              Node<5, End, End> > >,
                               Node<5, End, End> > tree2;
 
        std::cout << Add<tree1>::value << std::endl; 
        std::cout << Height<tree1>::value << std::endl;
 
        std::cout << Add<tree2>::value << std::endl; 
        std::cout << Height<tree2>::value << std::endl;

6.3. Runtime Generative Binary Recursion

In merge sort we subdivide our array (or vector) in two pieces and keep doing this until there is only one element left in the sub array, and then we merge all the sub arrays together. The splitting piece of this program is quite straight forward and the real fun part is in the mergeVectors function. We can implement the mergeVectors function in two ways. Either we can create a new temporary vector and insert elements into it or we simply swap the values of existing vectors. In this program we use the second approach i.e. swap the values of existing vectors 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 
                       // whih are greater than current value 
                       // to make room for currnet value to insert at the 
                       // first place of 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); 
}

Here is simple usage of this function.

mergeSort(vec.begin(), vec.end());

6.4. Compile Time Generative Binary Recursion

Fibonacci number is perhaps the simplest implementation of generative binary recursion. In simplest implementation, to calculate any Fibonacci number other than the first two, we first have to calculate the last two Fibonacci numbers. Here is simple implementation of this.

template <int n> struct Fib 
{ 
        // binary recursive call 
        enum { value = Fib<n - 1>::value + Fib<n - 2>::value }; 
}; 
 
// termination condition 
template<> struct Fib<2> 
{ 
        enum { value = 1 }; 
}; 
 
// termination condition 
template <> struct Fib<1> 
{ 
        enum { value = 1 }; 
};

Here is a simple usage of this function.

std::cout << Fib<16>::value << std::endl;

7. Nested Recursion

This is a special type of recursion when the recursive call is nested. All of the above recursion we can replace them with either simple looping or loop with stack, but this type of recursion cannot be easily replaced by 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. Runtime Structure Nested Recursion

Nested Link List can be a good example of Structured Nested Recursion. In 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 nested link list, every node of a link list contains two addresses. The first address is just like a simple link list contains the address of 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 we 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 Matrix. We can't make a 2D array with every row containing different number of elements.

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

Here is a simple example of both types of nodes and nested recursive implementation to display the values of the nested link list. Here we have recursive TraverseNode method, which internally calls PrintNestedList method that is also a recursive function. TraverseNode prints the outer link list and PrintNestedList, as the name suggests, prints the values of 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; 
        } 
};
// 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 a simple usage of 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. Compile Time Structure Nested Recursion

In a similar way we can create a nested link list at compile time. Here we defined two node types, just like the runtime version. In addition we have to define two different end markers, one for link list and the other for nested link list name End and NestedEnd respectively.

// Termination of Link List 
struct End 
{ 
};
 
// Node of Static Link List 
template <int iData, typename Type> 
struct Node 
{ 
        enum { value = iData }; 
        typedef Type Next; 
};
 
// Termination of Nested Link List
struct NestedEnd
{
};
 
// Node of Nested Link List
template <int iData, typename NestedType, typename Type>
struct NestedNode
{
        enum { value = iData };
        typedef NestedType     NestedList;
        typedef Type           Next;
};

Instead of printing the value of nested link list here we are going to count the values in link list and nested link list. Here Count is a structure that recursively instantiates itself as well as Length structure too. Length structure also instantiates itself to calculate the length of nested link list.

// Structure to calculate the length of Static Link List 
template <typename T> 
struct Length; 
 
// Partial Template Specialization call recursiveely 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 calculate the number of elements in Nested Static Link List 
template <typename T> 
struct Count; 
 
// Partial Template Specialization call recursiveely calculate the length 
template <int iData, typename NestedType, typename Type> 
struct Count<NestedNode<iData, NestedType, Type> > 
{ 
        enum { value = 1 + Count<Type>::value + Length<NestedType>::value }; 
}; 
 
template <>
struct Count<NestedEnd>
{
        enum { value = 0 };
};

Here is simple usage of these structures.

// Nested Link List
// first nested link list contains elements multiple of 5
// second nested link list contains natural numbers
// third nested link list contains prime number
typedef NestedNode<100, Node<5, Node<10, Node<15, End> > >, 
               NestedNode<200, Node<1, Node<2, Node<3, Node<4, Node<5, Node<6, End> > > > > >, 
               NestedNode<300, Node<2, Node<3, Node<5, Node<7, Node<11, Node<13, Node<17, End> > > > > > >, 
                       NestedEnd> > > nestedList;
 
std::cout << Count<nestedList>::value << std::endl;

7.3. Runtime Generative Nested Recursion

McCarthy function, also known as McCarthy 91 function, is a nested recursive function defined by John McCarthy. This function is proposed as a test case for formal verification of the system. This is also known as McCarthy 91 function because for every value less than 100 this function returns 91.

Here is a mathematical formula of this function.

[Recursion_03_10.jpg]
Figure 10: McCarthy Function

Here is simple implementation of this function.

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

Here is simple usage of this function.

std::cout << McCarthy(25) << std::endl;

7.4. Compile Time Generative Nested Recursion

One more example of a nested recursive function is Ackermann function. This function explodes very rapidly; therefore it is usually used to check the compiler's ability to optimize recursion. Here is mathematical formula for Ackermann function.

[Recursion_03_11.gif]
Figure 11: Ackermann Function

This is simple compile time implementation of this nested function.

template <int m, int n> 
struct Ackermann 
{ 
        // nested recursive call 
        enum { value = Ackermann<m-1, Ackermann<m, n-1>::value>::value }; 
}; 
 
template <int m> struct Ackermann<m, 0> 
{ 
        // linear recursive call 
        enum { value = Ackermann<m-1, 1>::value }; 
}; 
 
// termination condition 
template <int n> 
struct Ackermann<0, n> 
{ 
        enum { value = n + 1 }; 
};

Here is a usage of this function.

std::cout << Ackermann<2, 3>::value << std::endl;

8. References

1. 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.
2. Concrete Mathematics 2nd edition
   Ronald L. Graham, Donald E Knuth, Oren Patashnik
3. 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/
4. Recursion Primer Using C++: Part 2
   Zeeshan Amjad
   http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_02.aspx
   http://www.codeguru.com/cpp/cpp/algorithms/math/print.php/c15693__4/