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:
- Compiling and Running Factorial
Cut and paste the following code into an empty program.
int Factorial(int Num)
// Terminating condition
if (Num <= 1)
// Recursive case
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.
- Tracing Factorial Execution
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.
- Compiling and Running Fibonacci
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)
// Recursive case
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.
- Tracing Fibonacci Execution
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.
- Calculating X^p Recursively
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.
int 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.
- Improving X^p
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.
- Submit Work
This lab assignment will be submitted electronically
to the TAs once you fill in the fields below and
click on the "submit" button. You do NOT need to print
a copy of this document to hand in.