Wrox Press C++ Tutorial

Recursive Function Calls

When a function contains a call to itself, it's referred to as a recursive function. A recursive function call can also be indirect, where a function fun1 calls a function fun2, which in turn calls fun1.

Recursion may seem like a recipe for an infinite loop, and if you aren't careful it certainly can be. An infinite loop will lock up your machine and require Ctrl-Alt-Del, which is always a nuisance. A prerequisite for avoiding an infinite loop is that the function contains some means of stopping the process.

Unless you have come across the technique before, the sort of things to which recursion may be applied may not be obvious. In physics and mathematics there are many things which can be thought of as involving recursion. A simple example is the factorial of an integer which for a given integer N, is the product 1x2x3...xN. This is very often the example given to show recursion in operation. However, we shall look at something even simpler.

Try It Out - A Recursive Function

At the start of the chapter (see Ex4_01.cpp) we produced a function to compute the integral power of a value, that is to compute xn. This is equivalent to x multiplied by itself n times. We'll implement this as a recursive function as an elementary illustration of recursion in action.

// Ex4_12.cpp (based on Ex4_01.cpp)
// A recursive version of x to the power n
#include <iostream>
#include <cstdlib>             // This is for the exit() function
using namespace std;

double power(double x, int n); // Function prototype

int main(void)
{
   int index = 3;     // Raise to this power
   double x = 3.0;    // Different x from that in function power
   double y = 0.0;
   y = power(5.0, 3); // Passing constants as arguments

   cout << endl
        << "5.0 cubed = " << y;

   cout << endl
        << "3.0 cubed = "
        << power(3.0, index);     // Outputting return value

   // Using a function as an argument
   x = power(x, static_cast<int>(power(2.0, 2)));

   // with auto conversion of 2nd parameter
   cout << endl 
        << "x = " << x;

   cout << endl;
   return 0;
}

// Recursive function to compute integral powers of a double
// value - first argument is a double value, and the second
// argument is a power index.
double power(double x, int n)
{
   if(n<0)
   {
      cout << endl
           << "Negative index, program terminated.";
      exit(1);
   }
   if(n)
      return x*power(x, n-1);
   else
      return 1.0;
}

The function main() is exactly the same as the previous version so the output is also the same:

We have added the #include statement for cstdlib, because we use the exit() function in our revised function power(). Let's now look at how the function works.

How It Works

We only intend to support positive powers of x, so the first action is to check that the value for the power that x is to be raised to n, is not negative. This is essential for our implementation of a recursive function, otherwise we could get an infinite loop with negative values for n because of the way the function is written. The if statement provides for the value 1.0 being returned if n is zero, and in all other cases it returns the result of the expression, x*power(x, n-1). This causes a further call to the function power() with the index value reduced by 1.

Clearly, within the function power(), if the value of n is greater than zero, a further call to the function power() will occur. In fact, for any given value of n greater than 0, the function will call itself n times. The mechanism is illustrated in the following figure, assuming the value 3 for the index argument.

As you see, we need a total of four calls to the power() function to generate x3.

Using Recursion

Unless you have a problem which particularly lends itself to using recursive functions, or if you have no obvious alternative, it's generally better to use a different approach, such as a loop. This will be much more efficient than using recursive function calls. Think about what happens with our last example to evaluate a simple product, x*x*...x, n times. On each call, the compiler will generate copies of the two arguments to the function, and also has to keep track of the location to return to when each return is executed. It's also necessary to arrange to save the contents of various registers in your computer so that they can be used within the function power(), and of course these will need to be restored to their original state at each return from the function. With a quite modest depth of recursive call, the overhead can be considerably greater than if you use a loop.

This is not to say you should never use recursion. Where the problem suggests the use of recursive function calls as a solution, it can be an immensely powerful technique, greatly simplifying the code. We'll see an example where this is the case in the next chapter.

© 1998 Wrox Press