At Last!!!

Advanced Programming
Recursion Using C++

Introduction

A recursive function is a function that calls itself either directly or through another function. Recursion can be direct or indirect. It is direct recursion when a function calls itself; it is indirect recursion when a function calls another function and that function calls the first function.

It is important to note that when a function calls itself, a new copy of that function is run. The local variables in the second version are independent of the local variables in the first, and they cannot affect one another directly, any more than the local variables in the main() function can affect the local variables in any function it calls.

All recursive functions can be replaced by iterative functions. Iteration solutions are often better than recursion with respect to performance, because recursion produces a series of function calls and copies of variables, requiring more overhead, that iteration can avoid. Recursion is most effective when it mirrors the real-world problem more naturally than iteration, thus the program is easier to understand and debug.

Some problems are most easily solved by recursion, usually those in which you act on data and then act in the same way on the result.

Examples

Below are two examples that use both iteration and recursion to solve the stated problem. You should compare these approaches in terms of coding complexity, how well they model the problem and, perhaps, in computer resources needed (e.g., time to completion).

GCD Example

In mathematics, the greatest common divisor (gcd) of two non-zero integers, is the largest positive integer that divides both numbers without remainder.

The greatest common divisor of a and b is usually written as gcd(a, b) and read as "gcd of a and b.". For example, gcd(12, 18) = 6, gcd(-4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

Euclid's Algorithm. Given two natural numbers a and b, not both equal to zero:

1. check if b is zero
2. if yes, a is the gcd
3. if not, repeat the process using, respectively, b, and the remainder after dividing a by b.

The remainder after dividing a by b is usually written as a mod b). In C++ we implement a mod b using the % operator.

Using Iteration

The following program finds the greatest common divisor using iteration and Euclid's algorithm. For simplicity, we "hard code" two test cases in the program itself.

// gcdLoop
#include 
using namespace std;

int GreatestCommonDivisor(int, int);

int main()
{
 int a,b,gcd;
 a = 25;
 b = 15;

 gcd = GreatestCommonDivisor(a, b);
 cout << "The GCD of " << a  << " and "
      << b << " is " << gcd << endl;

 a = 129;
 b = 48;
 gcd = GreatestCommonDivisor(a, b);
 cout << "The GCD of " << a  << " and "
      << b << " is " << gcd << endl;

 return (0);
}

// Using Euclid's algorithm
int GreatestCommonDivisor(int x, int y)
{
 while (y != 0)
 {
   const int temp = y;
   y = x % y;
   x = temp;
 }
 return x;
}

Compiling and running this program on the course server yields the following output.

et791:~/cset3150$ ./gcdLoop 
The GCD of 25 and 15 is 5
The GCD of 129 and 48 is 3
et791:~/cset3150$ _

Try it! Cut-and-paste this program to the course server. Compile and run it to verify that it works.

Change it. Use several different sets of test values and confirm the accuracy of the program's results. Note that in changing the program to include different sets of test values, you will be changing the main() function - not the GreatestCommonDivisor() function.

Using Recursion

The program below finds the greatest common divisor using Euclid's algorithm and a recursive function.

// gcdRecursion
#include 
using namespace std;

int GreatestCommonDivisor(int, int);

int main()
{
 int a,b,gcd;
 a = 25;
 b = 15;

 gcd = GreatestCommonDivisor(a, b);
 cout << "The GCD of " << a  << " and "
      << b << " is " << gcd << endl;

 a = 129;
 b = 48;
 gcd = GreatestCommonDivisor(a, b);
 cout << "The GCD of " << a  << " and "
      << b << " is " << gcd << endl;

 return (0);
}

// Using Recursion
int GreatestCommonDivisor(const int x, const int y)
{
 if (y==0) return x;
 return GreatestCommonDivisor(y,x%y);
}

Compiling and running this program on the course server yields the following output.

et791:~/cset3150$ ./gcdRecursion 
The GCD of 25 and 15 is 5
The GCD of 129 and 48 is 3
et791:~/cset3150$ _

This is identical to the result for the iterative version (gcdLoop.cpp) shown previously.

Try it! Compile and run the program in your own directory on the course server.

Change it. Rewrite the program above to accept input from the user for the two values.

Factorial Example

A common example used to illustrate recursion is the factorial function. The factorial of a non-negative integer n is defined as follows, where the notation n! means "the factorial of n."

0! = 1
n! = n * (n-1) * (n-2) * ... * 2 * 1   for n > 0

So we would find the following:

0! = 1
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

This definition of the factorial function leads easily to a normal iterative factorial function.

Using Iteration

The program below is written to implement and test the iterative version of the factorial function.

// compute the factorial of n using iteration
#include 
using namespace std;

long factorial(int);

int main()
{
 int a,fact;

 a = 5;
 fact = factorial(a);
 cout << "The Factorial of " << a
      << " is " << fact << endl;

 a = 9;
 fact = factorial(a);
 cout << "The Factorial of " << a
      << " is " << fact << endl;

 a = 12;
 fact = factorial(a);
 cout << "The Factorial of " << a
      << " is " << fact << endl;

 return (0);
}

long factorial(int n)
{
 int i;
 long result = 1;

 for (i = 2; i <= n; i++)
 {
    result = result * i;
 }

 return (result);
}

Compiling and running the program above on the course server yields the following output.

et791:~/cset3150$ ./factLoop 
The Factorial of 5 is 120
The Factorial of 9 is 362880
The Factorial of 12 is 479001600
et791:~/cset3150$ _

Try it! Compile and run the program in your own directory on the course server.

Change it. Rewrite the program above to accept input from the user for the value of the factorial to be calculated. What happens if the input value is 24? Can you explain this result?

Using Recursion

To write a recursive version of the factorial function, we note the following:

0! = 1
1! = 1
2! = 2 * 1 = 2 = 2 * 1!
3! = 3 * 2 * 1 = 6 = 3 * 2!
4! = 4 * 3 * 2 * 1 = 24 = 4 * 3!
5! = 5 * 4 * 3 * 2 * 1 = 120 = 5 * 4!

In other words, n factorial is simply n times n -1 factorial.

This slightly different view of the factorial definition leads to a recursive factorial function. This could be written as shown in the program example below:

// compute the factorial of n using recursion
#include 
using namespace std;

long factorial(int);

int main()
{
 int a,fact;

 a = 5;
 fact = factorial(a);
 cout << "The Factorial of " << a
      << " is " << fact << endl;

 a = 9;
 fact = factorial(a);
 cout << "The Factorial of " << a
      << " is " << fact << endl;

 a = 12;
 fact = factorial(a);
 cout << "The Factorial of " << a
      << " is " << fact << endl;

 return (0);
}

long factorial(int n)
{
 if ((n == 0) || (n == 1))   // base cases
 {
    return (1);
 }
 else                        // recursive case
 {
    return n * factorial(n - 1);
 }
}

Compiling and running the program above on the course server leads to the following output.

et791:~/cset3150$ ./factRecursion 
The Factorial of 5 is 120
The Factorial of 9 is 362880
The Factorial of 12 is 479001600
et791:~/cset3150$ _