Recursion Primer Using C++ Part 3

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.

Dimensions of Recursion
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.

Runtime Recursive Algorithms
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.

Compiletime Recursive Algorithms
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.

Types of Recursion
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.

McCarthy 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.

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/

More by Author

Must Read