Recursion Primer Using C++, Part 1

1. Introduction

In general, recursion means self-repeating patterns. In mathematics, it can be a function that is defined in terms of itself, such as factorial, Fibonacci, and so forth. In computer programming, recursion means a function that is defined in terms of itself. In other words, it is a function that calls itself. Every recursive function has a termination condition; otherwise, it will call itself forever, and this condition can be called a base condition.

Usually, recursion is a little bit difficult for most students to understand. Researchers usually come up with different strategies to teach recursion easily for students, such as teach recursion before arrays [4], delegation [2], or recursively generated geometric designs [3].

2. Types of Recursion

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.

In C++, we also can do compile time recursion with the help of template meta-programming. When you instantiates the template class (or structure) in C++, the compiler will create the code of that class at compile time. Just like run time recursion, you can instantiate the template class itself to perform the recursion. Just like run time recursion, you also need the termination condition; otherwise, instantiation will go forever, at least theoretically, but of course it is limited to the resources of the computer and compiler. In this meta-programming template, you can specify the termination condition (or base condition) with the help of template specialization or partial template specialization, depending on the termination condition.

One can thing that might do the same thing with the C++ preprocessor is to use macros because they also will replaced during compilation. In fact, technically a preprocessor replaces all the macros even before compilation, so it is not performing at compile time. The preprocessor also has lots of limitations; because of simple text replacement, there is no debug symbol define for the debugger, but the most critical limitation is that it can not be recursive. The section 16.3.4.2 standard of C++ [1] strictly restricts one to write macros that call themselves recursively; therefore, you can't do recursive programming in macros, just like you used to do in template programming.

The other way to see the recursion is by how the recursive algorithm is implemented. A recursive algorithm can be implemented in more than one way, such as linear, tail, mutual, binary, or nested recursion. You can implement them either at compile time using template meta-programming or at run time using function or member functions.

You can represent different types of recursion in the following diagram. This diagram shows the different types of recursion depending on their implementation—in other words, linear, tail, mutual, and so forth—and when it will be performed.

Now you will explore different type of algorithms one by one and take a look at their run time as well as compile time implementations.

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.

A function may perform some additional tasks during winding or unwinding; in the case of a factorial, it will multiply the input number with the return value of the function during the unwinding phase. This process can be demonstrated with the following diagram (shown below) that shows both the winding and unwinding phases of a factorial function using linear recursion.

Mathematically, you can write the factorial function recursively this way; in other words, when the value of "n" is zero, return one and when the value of "n" is greater than zero, call the function recursively with "n-1" and multiply the result with the return value of the recursive function.

int Factorial(int no)
{
   // error condition
   if (no < 0)
      return -1;

   // termination condition
   if (0 == no)
      return 1;

   // linear recursive call
   return no * Factorial(no - 1);
}

Program 1: Run time example of Linear Recursion

The preceding program is a run time version of linear recursion. Here, you have a termination condition of 0; this program starts doing unwinding when it reaches the termination condition. There is one more error condition in this program to prevent an infinite function call if someone passed a negative number to this function. This function will simply return -1 as an error if the value of the parameter is negative.

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

// termination condition
template <>
struct Factorial<0>
{
   enum { value = 1 };
};

Program 2: Compile time example of Linear Recursion

This program is a compile time counterpart of Program 1. Here, you use the template instantiation to perform the recursion. You also have a termination condition in the form of template specialization. This is a very simple example of template specialization and does not have a lot of code, but in a few cases, you might have to rewrite all the code in the template specialization class (or structure) too, because you can't inherit the code from the template class (or structure) to specialize the class (or structure).

Here, you didn't even introduce the error condition of a negative number because this program wont even compile if someone tries to call this with a negative number. This is one very big advantage of compile time recursion that you even couldn't compile the infinite calling condition. However, the error message is perhaps not very obvious in that case.

Here is the usage of compile time recursion.

cout << Factorial<6>::value  << endl;
cout << Factorial<0>::value  << endl;
cout << Factorial<-2>::value << endl;

Here, the compiler will refuse to compile the last statement and give a long, cryptic error message.

Recursion Primer Using C++, Part 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 is usually more efficient because a smart compiler will automatically convert this recursion 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 of this, they simply return the value of the recursive function call. Here is an example of the same program converted into tail recursion.

You can define tail recursion mathematically by using this equation; in other words, when the value of "n" is zero, simply return the value of "a"; if the value of "n" is greater than zero, call the recursive function by passing "n-a" and "n*a". Here, you also can notice that during the unwinding phase every recursive function simply returns the value of "a".

int Factorial(int no, int a)
{
   // error condition
   if (no < 0)
      return -1;

   // termination condition
   if (0 == no || 1 == no)
      return a;

   // Tail recursive call
   return Factorial(no - 1, no * a);
}

Program 3: Run time example of tail recursion

This is a modified version of a linear recursion program. You perform all the calculations before calling the recursive function, and simply return the value of whatever you got from the recursive function. Here, the calculation order is the reverse of the linear recursion. In linear recursion, you first multiply 1 by 2; its result with; 3 and so on. On the other hand, here you multiply n with n-1, and then with n-2 until you reach 0.

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

Program 4: Compile time example of tail recursion

Here is the compile time version of the same program doing the same thing at compile time.

Tail Recursion is very useful and sometimes unavoidable in functional languages because they might not have a looping construct. They usually perform the looping with the help of tail recursion. You can do almost everything with tail recursion that can be done with looping, but this is usually not true in reverse. Here is a very simple example to demonstrate the looping via tail recursion.

// implement looping via tail recursion
// simple version
void RecursiveLoop(int n)
{
   // termination condition
   if (0 == n)
      return;

   // action to be performed
   cout << n << endl;

   // tail recursive call
   return RecursiveLoop(--n);
}

Program 5: Demonstration of Looping via trail recursion simple version

But, this program looks very rigid and you cannot customize it. With the help of the template and function objects, you can customize this function so you can control each and individual piece of it. Here is a modified version of the same program where you can control each and every part of it.

// implement looping via tail recursion
// template version
template <typename TType, typename TTerminate, typename TAction,
          typename TStep>
void RecursiveLoop(TType n)
{
   // termination condition
   if (TTerminate()(n))
      return;

   // action to be performed
   TAction()(n);

   // tail recursive call
   return RecursiveLoop<TType, TTerminate, TAction,
                        TStep>(TStep()(n));
}

Program 6: Demonstration of Looping via the trail recursion template version

Here is the default implementation of "Termination condition", "Action to be performed", and "Stepping out of the loop".

// user-defined termination condition
template <typename T>
class IsTerminate
{
public:
   // operators used in this function
   // must be overloaded for given type T
   bool operator () (T n)
   {
      return n == 0 ? true : false;
   }
};

// user-defined step condition
template <typename T>
class Step
{
public:
   // operators used in this function 
   // must be overloaded for given type T
   T operator () (T n)
   {
      return --n;
   }
};

// user-defined actions
template <typename T>
class Action
{
public:
   // operators used in this function
   // must be overloaded for given type T
   void operator () (T n)
   {
      cout << n << endl;
   }
};

Program 6: Implementation of each step for recursive loop via the tail recursion template version.

And here is the simple usage of this function.

// usage of tail recursive loop
// template version
RecursiveLoop<int, IsTerminate<int>, Action<int>, Step<int> >(10);

You cannot give the default implementation in the "RecursiveLoop" function because C++ doesn't allot the default template parameter to a function template. You can do this only in the case of a C++ class. To overcome this situation, you can make a "RecursiveLoop" function object instead of a simple function and pass the default action as a default parameter, so its calling will be much simpler. Here is the revised version of the existing program.

template <typename TType,
   typename TTerminate = IsTerminate<TType>,
   typename TAction = Action<TType>, 
   typename TStep = Step<TType>
>
class RecursiveLoop
{
public:
   void operator ()(TType n)
   {
      // termination condition
      if (TTerminate()(n))
         return;

      // action to be performed
      TAction()(n);

      // tail recursive call
      return RecursiveLoop<TType, TTerminate, TAction,
                           TStep>()(TStep()(n));
   }
};

Program 7: Impalement the looping via tail recursion using the function object and default template parameter.

Now, the usage of this function object is very simple.

//Usage of function object implementaion of recursive loop
RecursiveLoop<int>()(10);

Recursion Primer Using C++, Part 1

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 you to call a function recursively. The termination condition in this recursion can be in one or all functions.

Mathematically, you can define these functions as

bool isEven(int no)
{
   // termination condition
   if (0 == no)
      return true;
   else
      // mutual recursive call
      return isOdd(no - 1);
}

bool isOdd(int no)
{
   // termination condition
   if (0 == no)
      return false;
   else
      // mutual recursive call
      return isEven(no - 1);
}

Program 8: Run time example of mutual recursion

This is the most primitive example of mutual recursion. You know that zero is an even number and 1 is an odd number. If you want to check whether is number is even or odd, you can call these functions; those internally call each other by subtracting one from the input value until it reaches the base condition. Of course, this is not the best way to implement this algorithm; it will take a lot of resources to check whether the number is even or odd. In addition, if someone passed a negative number, they will keep calling each other and eventually throw a stack overflow error at run time.

template <int no>
struct isEven
{
   // mutual recursive call
   enum { value = no == 0 ? 1 : isOdd<no - 1>::value };
};

// termination condition
template <>
struct isEven<0>
{
   enum { value = 1 };
};

template <int no>
struct isOdd
{
   // mutual recursive call
   enum { value = no == 0 ? 0 : isEven<no - 1>::value };
};

// termination condition
template <>
struct isOdd<0>
{
   enum { value = 0 };
};

Program 9: Compile time example of mutual recursion

Here is the compile time version of the same program. The only difference between this program and the one above is that it will not even compile if you try to a pass negative number to it.

Determining whether a number is even or odd by using mutual recursion is not a very good idea. A more interesting example is the male sequence and female sequence. Both function are recursively calling each other and can be defined as the following.

Here are the run time and compile time versions of the male and female function using mutual recursion.

int MaleSequence(int n)
{
   // termination condition
   if (0 == n)
      return 0;

   // mutually recursive call
   return n - FemaleSequence(MaleSequence(n-1));
}

int FemaleSequence(int n)
{
   // termination condition
   if (0 == n)
      return 1;

   // mutually recursive call
   return n - MaleSequence(FemaleSequence(n-1));
}

Program 10: Run time mutual recursion implementation of Male and Female functions.

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

As with other compile time recursion functions, you have to do template specialization for both functions to handle the termination condition.

Recursion Primer Using C++, Part 1

6. Binary Recursion

In binary recursion, the recursive function calls itself twice, not once. This type of recursion is very useful with some data structures, such as 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 case of binary two). In other words, recursive functions call exponentially in this type of recursion.

Mathematically, you can define the Fibonacci sequence as

int Fib(int no)
{
   // error condition
   if (no < 1)
      return -1;

   // termination condition
   if (1 == no || 2 == no)
      return 1;

   // binary recursive call
   return Fib(no - 1) + Fib(no - 2);
}

Program 12: Run time example of binary recursion

Here is the simple implementation of Fibonacci numbers calling the recursive function twice. Here, you have two base cases; when the value of input parameter is 1 and 2. This, of course, is not the best implementation of a Fibonacci number and you can convert it into tail recursion by changing it a little bit. But, before converting this one into tail recursion, take a look at the compile time version of binary recursion.

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

Program 13: Compile time example of binary recursion

In the compile time version of binary recursion, you specialize the template class (or structure) twice. In general, you have to do template specialization every base case.

int Fib(int n, int a, int b)
{
   // termination condition
   if (1 == n)
      return b;
   else
      // tail recursive call
      return Fib(n-1, b, a+b);
}

Program 14: Run time example of converting binary recursion into tail recursion

Here, you convert the binary recursion into tail recursion. You simply perform the calculation before calling any recursive function; therefore, you do not need to call the recursive function twice. In a Fibonacci number, you always need the last two numbers, so after performing the calculation on the last two numbers, you just discard the first one—in this case, "a"—and replace the second one in place of first—place the value of "b" in the case of "a" and calculate the next number.

Mathematically, you can define it as

template <int n, int a, int b>
struct Fib
{
   // tail recursive call
   enum { value = Fib<n-1, b, (a+b)>::value };
};

// termination condition
template<int a, int b>
struct Fib<1, a, b>
{
   enum { value = b };
};

Program 15: Compile time example of converting binary recursion into tail recursion

Here is the compile time version of this program. Here, you have only one termination condition (base case); therefore, you need only one template specialization. You perform partial template specialization because you want the last calculated value in the base case when the value of n is equal to 1.

7. Nested Recursion

This is a special type of recursion, when the recursive call is nested. In all of the above recursion, you can replace them with either simple looping or a loop with stack, but this type of recursion cannot be replaced easily by a simple loop.

One typical example of nested recursion is the Ackermann function. Here is the simple diagram of an Ackermann function to demonstrate the nested recursion. You explicitly selected the small value of this as a parameter for simplicity.

Mathematically, an Ackermann function is defined as

int Ackermann(int m, int n)
{
   // error condition
   if (m < 0 || n < 0)
      return -1;

   // termination condition
   if (0 == m)
      return n + 1;

   // linear recursive call
   else if (m > 0 && 0 == n)
      return Ackermann(m-1, 1);

   // nested recursive call
   else
      return Ackermann(m-1, Ackermann(m, n-1));
}

Program 16: Run time example of nested recursion

Here is the run time implementation of nested recursion. This function has two termination conditions; one condition terminates the nested calls and starts performing linear recursion; the other termination condition stops the linear recursion. The first "if" condition is for error checking.

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

Program 17: Compile time example of nested recursion

In the compile time version of a nested call, you have to do template specialization twice because of two termination conditions. The first specialization stops the nested call and starts doing linear recursion; the second specialization stops the linear recursion.

Recursion Primer Using C++, Part 1

8. Template Recursion

All the programs explained above are either running completely at compile time or at run time. You can make a program that can use both compile time as well as run time features. One such example is instantiating the object at compile time using compile time recursion and then use it at run time. For example, if you want to create a class of a multi dimension array, you can pass the dimension, with its type, as a parameter and create an object of the same class with one less dimension inside. When the dimension reaches the one, you can stop it with template specialization and provide an implementation of a one-dimension array. You can represent this concept with the following diagram.

Here is the simple implementation of this. Just to make it simple, I avoid const correctness, use std::vector, and give the minimum possible interface of this class.

template <typename T, int Dim>
class Array
{
private:
   // recursively create object
   Array<T, Dim - 1> vecRow;

public:
   Array(int iSize = 0)
   {
      vecRow.Resize(iSize);
   }

   void Resize(size_t iSize)
   {
      vecRow.Resize(iSize);
   }

   size_t Size()
   {
      return vecRow.Size();
   }

   Array<T, Dim - 1>& operator [] (size_t x)
   {
      if (x >= 0 && x < vecRow.Size())
      {
         return vecRow;
      }

      throw std::out_of_range("Index is out of range");
   }

};

// specialized class to stop recursion
template <typename T>
class Array<T, 1>
{
private:
   std::vector<T> vecRow;

public:
   Array(int iSize = 10)
   {
      Resize(iSize);
   }

   void Resize(size_t iSize)
   {
      vecRow.resize(iSize);
   }

   size_t Size()
   {
      return vecRow.size();
   }

   T& operator [] (size_t x)
   {
      if (x >= 0 && x < vecRow.size())
      {
         return vecRow.at(x);
      }

      throw std::out_of_range("Index is out of range");
   }
};

Program 18: Multi dimension class using template recursion

Here is the usage of this class.

Array<int, 3> obj(10);

obj[0][0][0] = 100;
obj[0][1][0] = 200;
obj[1][2][0] = 300;
obj[0][3][0] = 400;

In this example, object creation is performed at compile time using template recursion technique. Once the object is created, its method will be called at run time.

9. Acknowledgment

I'd like to say thanks a lot to "Tafseer Ahmed" and "Shahzaib Saleem" for reading this and giving me their useful comments about this and point out several mistakes in the initial draft to make it better.

10. References

  1. Programming Language ISO/IEC 14882, 2003
  2. "Teaching and viewing recursion as delegation" by Jeffrey Edgington
  3. "Teaching recursion using recursively generated geometric design" by Aaron Gordon
  4. "Why Structure Recursion should be taught before Arrays in CS1" by Kim B. Bruce, Andrea Danyluk, Thomas Murtagh


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

  • Java developers know that testing code changes can be a huge pain, and waiting for an application to redeploy after a code fix can take an eternity. Wouldn't it be great if you could see your code changes immediately, fine-tune, debug, explore and deploy code without waiting for ages? In this white paper, find out how that's possible with a Java plugin that drastically changes the way you develop, test and run Java applications. Discover the advantages of this plugin, and the changes you can expect to see …

  • Savvy enterprises are discovering that the cloud holds the power to transform IT processes and support business objectives. IT departments can use the cloud to redefine the continuum of development and operations—a process that is becoming known as DevOps. Download the Executive Brief DevOps: Why IT Operations Managers Should Care About the Cloud—prepared by Frost & Sullivan and sponsored by IBM—to learn how IBM SmartCloud Application services provide a robust platform that streamlines …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds