Lab Three: Recursion, part 1
Purpose:
This lab will introduce you to
the concept of recursion. By the end of
this lab, you will be able to write simple recursive functions to do such
things as calculate mathematical functions, print sets of parentheses, and
other things.
Prerequisites:
You should have an idea about what recursion is, but no knowledge beyond that is necessary.
Introduction:
We’ve seen examples throughout Computer Science I of functions that call other functions. As it turns out, a function in C++ can call any other function in the program – including itself! While this may seem strange, it leads to a central topic in computer science – recursion. Recursion is a central theme in computer science, and leads to many powerful algorithms.
There are two important things to remember when writing recursive functions:
· When you call the function, you should send it an input that is “smaller” than the input it received before the function call.
· You need to make sure that the recursion ends at some point – there should be some “small” input that does not result in a recursive function call.
This can be summed up in the two important parts of a recursive function:
· The base case – this is an input for which the answer can be computed without the need for a recursive function call. For example, if you are calculating the value of 2n for n = 0, you don’t need to do any calculations – the value is 1.
· The recursive case – this is an input for which the answer requires the answer to a “smaller” version of the same problem. For example, if you are calculating 2n for n = 100, you can figure out the answer by realizing that 2n = 2 ∙ 2n-1. So, if we can calculate 2n-1, we can figure out 2n easily.
The key to writing recursive function is to remember a few key points. First, you always need to have a base case – the recursion must always end. Part of this means that you have to make sure that the base case will always be reached – this may require more than one base case. Second, you have to “trust the magic” of recursion. If you get bogged down in what exactly is happening in all the function calls, you will have big problems. Just assume that the recursion will work, and calculate your answer accordingly. For example, don’t worry about how the value of 2n-1 is calculated; just assume that it is correct, and calculate 2n accordingly.
Procedure:
1. Copy the lab 3 files into your account, using the standard procedure.
2. The project file as written contains a program that gives the user a menu of choices. Each choice leads to a recursive function being called. However, the functions are not written yet – that is your job for this lab! You should notice that there are five functions that are not finished: factorial, power, nested, fibonacci, and lg. You will be finishing at least four of these functions in lab today.
3. You should start by writing the factorial function. Notice that this function takes one parameter – an integer n. This function will calculate the value of n! (said as “n factorial”). The function n! is defined as the value of all the numbers from 1 to n multiplied together. For example, 3! = 1 x 2 x 3 = 6 and 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720. 0! is defined to be 1. n! is not defined for negative numbers (you may assume your input is greater than or equal to zero). The factorial function is used in many areas of computer science and math, particularly combinatorics and permutations.
Some things to think about as you write the factorial function:
Make sure that you test your function thoroughly before moving on to the next step. What values do you think you should test it on?
4. Now move on to writing the power function. This function takes two parameters, one float called base and one integer called exp. The function should calculate the value of base raised to the exp power. For example, if base is 3 and exp is 2, then power( 3, 2 ) should return 9. Or, power( 1.5, 3 ) should return 3.375. For the basic power function, you should assume that the exponent is not a negative number (in other words, it is 0 or larger). For an extra challenge, make the power function work for any integer exponent.
Some things to think about as you write the power function:
Again, make sure you test your function thoroughly before moving on.
5. Now let’s write the nested function. This function takes one parameter, an integer called n. The function should print to the screen a set of n nested parentheses. For example, nested( 3 ) should print ((())). Clearly, it doesn’t make any sense to print a negative number of parentheses, so you can assume that n is not negative.
This function is not mathematical, so it might be a little more conceptually difficult. Again, some things to think about:
6. Let’s write the fibonacci function now. This function takes one parameter, an integer n. The function should return the n-th Fibonacci number. The Fibonacci numbers are a sequence of numbers with many properties that are useful in mathematics and computer science. The sequence starts at 0, where F0 = 0, F1 = 1, and each subsequent number is equal to the sum of the previous two. For example, F2 = 1, F3 = 2, F4 = 3, F5 = 5, and so on. In other words, the sequence of Fibonacci numbers is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …, where each number is equal to the sum of the previous two.
Complete the function. Consider the following thoughts while you write the function:
7.
Extra challenge. Complete
the code for the function lg.
This function has one parameter, an integer n. This function should return the value of the
log-base two of the number n. In
reality, it should return the integer equivalent of the log-base two of the
number – do this by rounding down the actual number. For example, lg(
2 ) should return 1 and lg( 11 ) should return 3.
We have discussed
the log-based two function in class a bit. Remember that the definition of the log-based
two is this: if n = 2x,
then x = lg( n ). In other words, lg( n
) is the power to which you have to raise 2 to get n. For example, 26 = 64, so lg( 64 ) = 6.
When writing the
function to calculate the log-base two of a number recursively, you need to
think about how you will do the calculation.
What “smaller” function call will you use to calculate the value of lg
( n )?
A hint might be found in a “rule of thumb” for calculating the log-base
two of a number – lg( n ) is roughly equal to
the number of times you can divide n by 2 before you get a value of 1.
Check your
function to make sure it gives values that you think are appropriate. The log of a number n is not defined
for any n that is not positive.
8.
You are finished!
Make sure that you get your lab checked off, and have a good day!
/*
lab3.cpp - This lab demonstrates the uses of recursion by having
you
write four
or five recursive functions.
Author: Scott Thede
Date:
*/
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
// Parameters:
An integer n.
// Pre: n
>= 0.
// Post: The
factorial of n is returned, assuming that it doesn't
//
overflow the value of an integer variable.
int factorial( int n ) {
// You write this.
}
// Parameters:
A float r, and an integer n.
// Pre: n
>= 0 (unless you are doing the extra challenge).
// Post: The
value of r to the n-th power is returned.
float power( float r, int n ) {
// You write this.
}
// Parameters:
An integer n.
// Pre: n
>= 0.
// Post: n
sets of nested parentheses are printed to the screen.
void nested( int n ) {
// You write this.
}
// Parameters:
An integer n.
// Pre: n
>= 0.
// Post: The
value of the n-th Fibonacci number is returned.
int fibonacci( int n ) {
// You write this.
}
// Parameters:
An integer n.
// Pre: n
> 0.
// Post: The
floor of the log-base 2 of n is returned (in other words,
//
it is rounded down to the nearest integer).
int lg( int n ) {
// You write this.
}
// Parameters:
None.
// Pre:
None.
// Post: The
menu of options is printed to the screen.
void printMenu( ) {
clrscr( );
cout << "Choose one of these options: "
<< endl;
cout << endl;
cout << "1.
Calculate a factorial." << endl;
cout << "2.
Calculate a power." << endl;
cout << "3.
Print a set of nested parentheses." << endl;
cout << "4.
Calculate a Fibonacci number." << endl;
cout << "5.
Calculate a log-base-2 value." << endl;
cout << "6.
End the program." << endl;
cout << endl;
}
// Parameters:
None.
// Pre:
None.
// Post: The
user has entered an integer, which is returned.
int getChoice( ) {
int ch;
cout << "Enter your choice here: ";
cin >> ch;
return ch;
}
// Parameters:
An integer ch.
// Pre:
None.
// Post: The
choice represented by ch is acted upon.
void processChoice( int ch ) {
int n;
float r;
switch( ch ) {
// Choice
1: factorial
case 1:
cout << "Enter a number, greater than or equal to
0: ";
cin >> n;
cout << "The factorial of " << n
<< " is " << factorial( n ) << endl;
break;
// Choice
2: power
case 2:
cout << "Enter a base: ";
cin >> r;
cout << "Enter an exponent: ";
cin >> n;
cout << "The value of " << r <<
" to the " << n << " power is "
<< power( r, n ) << endl;
break;
// Choice
3: nested parentheses
case 3:
cout <<
"Enter a number, greater than or equal to 0: ";
cin >> n;
cout << "Here is a set of " << n
<< " nested parentheses:" << endl;
nested( n );
cout << endl;
break;
// Choice
4: Fibonacci numbers
case 4:
cout << "Enter a number, greater than or equal to
0: ";
cin >> n;
cout << "The " << n << "-th
Fibonacci number is " << fibonacci( n )
<< endl;
break;
// Choice
5: log base 2
case 5:
cout << "Enter a number, greater than 0: ";
cin >> n;
cout << "The log-base-2 of " << n
<< " is " << lg( n ) << endl;
break;
// Choice
6: exit the program
case 6:
cout << "Thank you." << endl;
exit( 0 );
// Invalid
choice
default:
cout << "That was an invalid choice."
<< endl;
}
cout << "Press any key to continue."
<< endl;
getch();
}
// Main program
void main( ) {
int choice;
// Loops
forever, since the exit is handled in the processChoice
// function.
while( 1 ) {
printMenu( );
choice = getChoice( );
processChoice( choice );
}
}