The objective of this laboratory assignment is gain experience with recursion as a problem solving tool. We will also look at specific techniques for tracing and debugging recursive programs and estimating the computational "cost" of recursive programs. This assignment has the following steps:

Cut and paste the following code into an empty program.

int Factorial(int Num) { // Terminating condition if (Num <= 1) return(1); // Recursive case else return( Num * Factorial(Num-1) ); } 

In the main program, add code to prompt the user for a value of "Num" and call this function to calculate "Factorial(Num)". Test your program with a variety of values of "Num". What is the largest factorial value you can calculate? What happens if you enter a negative value? Cut and paste some sample program output below.

It is difficult to "see" what is going on when recursive functions are called to perform their task. One approach is to add print statements to indicate when each function is called and when a value is returned. Declare a variable "Return" which stores the return value when a value is being returned. Modify the Factorial function to include the following code at the top and bottom of the function respectively.

 cout << "Entering Factorial, Num = " << Num << endl; cout << "Leaving Factorial, Return = " << Return << endl; 

Now run your program a few times and save a sample output below. Hopefully, you can now visualize the function calling itself a little better.

The Fibonacci function is another classic example of recursion. The Fibonacci sequence was "invented" centuries ago by an Italian mathematician named John Smith (no actually his name was Fibonacci). The first 10 numbers in the Fibonacci sequence are: 1 1 2 3 5 8 13 21 34 55. Notice that the 3rd value is the sum of the 1st and 2nd values, the 4th value is the sum of the 2nd and 3rd values, etc. The recursive C++ function below will return the value in position "Num" in the sequence. For example, "Fibonacci(10)" will return 55.

int Fibonacci(int Num) { // Terminating condition if (Num <= 2) return(1); // Recursive case else return( Fibonacci(Num-1) + Fibonacci(Num-2) ); } 

Replace Factorial with Fibonacci in your program and recompile and test this function. Again, try a variety of "boundary" cases for "Num" to see what happens. What is the largest number in the Fibonacci sequence you can calculate? Cut and paste your new main program below.

You have probably guessed that the Fibonacci function makes more recursive calls to do its work than the Factorial function. To see just how nasty the situation is, add the following code to Fibonacci and redo your testing. Make sure you declare a variable "Return" to print the return variable when the functions returns a value as above.

 cout << "Entering Fibonacci, Num = " << Num << endl; cout << "Leaving Fibonacci, Return = " << Return << endl; 

It sure is amazing how much work is needed to calculate Fibonacci(10)! Pick a modest test case and cut and paste your program output below. If you look at this output closely you will see that the call sequence forms a "tree" this time instead of the straight "line" in the Factorial function.

Our previous recursive functions have taken a lot of function calls to get the job done. Recursion can also be use to perform calculations with less work than traditional methods. Calculating X^p (X raised to integer power p) is one example of this.

The slow way to calculate X^p is to multiply X by itself p times. The clever way to calculate X^p is to decompose it into smaller problems and combine the results to get the desired answer (divide and conquer). Consider the following function skeleton and pseudo-code.

float Power(float X, int p) { // Terminating conditions // if p is 0 then // X^p is 1 // if p is 1 then // X^p is X // Recursive cases // if p is an even number then // X^p = X^(p/2) * X^(p/2) // if p is an odd number then // X^p = X^(p/2) * X^(p/2) * X } 

If we use the slow approach to calculate X^16 it will require 15 multiplies. On the other hand, if we use the clever method, we can calculate X^16 in terms of X^8, and recursively calculate X^8 in terms of X^4, and so on until we get down to X^1 which is simply X. This means that we can calculate X^16 with only 4 multiplications, which is a huge savings.

Start with the function skeleton above, and add code to calculate X^p using the four pieces of information in the pseudo-code. HINT: You should store X^(p/2) in a temporary variable instead of calling the recursive function twice when you calculate X^p. Call your Power function with a range of p values, and save the results. Cut and paste your program and some of your results below.

Some of you may have tried running Power with a negative value of p, and you probably noticed that the function did not give the correct answer. We know that X^(-p) = 1 / X^p. This means you can calculate the value of Power with negative p's by calling Power again with a positive p value. Using this information, modify your function to use this fact so it works properly for negative p values. Try it out for 2-3 negative p values, and cut and paste your program output below.

Compiling and Running Factorial

Tracing Factorial Execution

Compiling and Running Fibonacci

Tracing Fibonacci Execution

Calculating X^p Recursively

Improving X^p