13: Recursion and Other Topics

What We Will Cover Reminders: Please silence all cell phones and pagers Sit at a computer station, start your computer and login When class is over, please shut down your computer. Remember that you lose any files not saved in the student folder. Continuations 13.1: Running Under Windows 13.1.1: About DLL's 13.1.2: Finding the DLL's You Need Exercise 13.1 13.1.3: Summary 13.2: Introduction to Recursion 13.2.1: About Recursion 13.2.2: Implementing Recursive Functions 13.2.3: How Recursion Works 13.2.4: Developing a Recursive Algorithm 13.2.5: Coding the Recursive Algorithm 13.2.6: Tracing the Execution 13.2.7: Using Recursion with Input Validation Exercise 13.2 13.2.8: Summary 13.3: Open Lab Wrap Up Due Next: Sampler Project (5/27/10) Continuations Questions from last class? Project Questions? Sampler Project (5/27/10) ^ top 13.1: Running Under Windows Learner Outcomes At the end of the lesson the student will be able to: Run console programs under Windows ^ top 13.1.1: About DLL's You can run your compiled programs under Windows, on computers without CygWin installed To accomplish this, you need to include the appropriate CygWin DLL's DLL stands for Dynamic Link Library A DLL is a binary file that provides a library of functions for use by programs All programs running under Windows use DLL's Any DLL that a program uses must be available on the computer where the application is running CygWin DLL's CygWin has a number of DLL's it provides These DLL's are located in the cygwin/bin directory They are easy to identify because they have an extension of .dll Your programs use one or more of these DLL's when they run Any DLL that your program uses must be accessible to the program Thus, to run your program on a computer without CygWin installed, you need to include a copy of the CygWin DLL's ^ top 13.1.2: Finding the DLL's You Need The easiest way to find the DLL's your program needs is to run the program under Windows Whenever the program needs a DLL, it attempts to load the DLL When it cannot load the DLL, it fails and identifies the DLL it needs To fix the problem, you copy the needed DLL into the same directory as your application Since the computers in our classroom have paths set to the Cygwin\bin directory, you need to delete the path setting for this test: path=. Example of Finding Needed DLL's We want to run the playagain.cpp program under Windows We save the program to the desktop and compile it using TextPad Next we launch a Windows console: From the Start menu, Select Run... In the text box type cmd and press the Enter key Then we remove the path to cygwin\bin by typing: path=. Now when we try to run the program, we get an error message We locate the CygWin DLL we need in the cygwin\bin directory and copy it to the desktop Now we can successfully run the application Example Application 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> using namespace std; int main() { string repeat = "y"; while ("y" == repeat) { cout << "\nPlaying an exciting game!\n"; cout << "Do you want to play again? (y/n) "; cin >> repeat; } cout << "\nThanks for playing!\n"; return 0; } ^ top Exercise 13.1 In this exercise we run a program under Windows without starting Cygwin or using TextPad. Specifications Choose an application, compile it and copy the .exe file to the desktop Open a Windows command line window: Click the Start button Select "Run..." In the Open box type in: cmd Press the Enter key Change to the Desktop directory: Y: cd Desktop Set the path on the computer to '.': path=. Run the .exe file and find the missing DLL's Copy the missing DLL's to the Desktop and run again ^ top 13.1.3: Summary You can run your compiled C++ programs under Windows To make your programs work, you need to include any required DLL's This is true for any Windows application The easiest way to find the needed DLL is to run your program When your program needs a DLL, Windows will try to load it When Windows cannot load the DLL, it gives an error message identifying the missing DLL To fix the problem, you copy the DLL into the directory in which you put your .exe file Check Yourself What is a DLL? Why do your programs need DLL's? How can you add the DLL's needed to make your program run? ^ top 13.2: Introduction to Recursion Learner Outcomes At the end of the lesson the student will be able to: Design recursive algorithms Code recursive functions Trace the processing steps of recursive functions ^ top 13.2.1: About Recursion Recursion: when an algorithm is defined in terms of itself. Recursion is a natural approach to some problems It allows us to break down a problem into one or more subproblems similar in form to the original problem Sounds circular, but in practice is not Recursion divides the problem into two parts: Recursive step Base case The recursive step solves part of the problem Then it calls the recursive step again and passes it the smaller problem Eventually the smaller problem becomes easy enough to just solve The easy-to-solve problem is known as the base case Recursion Example: Many Hands Make Light Work What if you were asked to do some repetitive task like washing the dishes? You look at the pile of dishes and realize you have better things to do So you wash one dish and then ask someone else to wash the dishes Then you leave as soon as possible The next person notices your actions and decides to do the same They wash one dish and then ask someone else to wash the dishes This sequence repeats until all the dishes are washed and the sink is empty Writing this as an algorithm, we have: Algorithm For Washing Dishes If the sink is empty, do nothing Else: Wash one dish Ask someone else to wash the dishes Recursive Elements Notice the recursive nature of the algorithm The "else" clause calls itself: To do the dishes, we ask someone else to do the dishes To make sure this algorithm is not an endless passing of the buck, each person does some work This makes the job passed to the next person smaller When all the dishes are done, the chain of asking someone else to do the dishes is broken ^ top 13.2.2: Implementing Recursive Functions Now that we see how recursion works, let us look at how to implement it in a program You implement recursion in C++ using functions Each function contains a conditional statement One of the conditions contains a call the the same function This structure is shown below: returnType recursiveFunction(parameters) { if (stopping condition) { // base case // Problem is very easy // so solve it and return } else { // recursive step // Solve part of the problem // leaving a smaller problem recursiveFunction(arguments); } } Like a loop, a recursive function must have some way to end Usually the base case is written first and the recursive step second The code below implements our recursive example Implementation of Recursive Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream> using namespace std; void wash(int count); int main() { int count; cout << "How many dishes to wash? "; cin >> count; wash(count); } void wash(int count) { if (count == 0) { cout << "Done washing dishes\n"; return; } else { cout << "Washing one dish; number remaining: "; count = count - 1; cout << count << endl; wash(count); } } ^ top 13.2.3: How Recursion Works To understand how recursion works, we must consider a data structure known as a stack A stack is like a pile of dishes: When a dish is placed on the stack, it is placed on top Similarly, when a dish is removed from the stack, it is taken from the top The last dish put on the stack is the first dish removed from the stack: Otherwise you get a lot of broken dishes Function Call Stack When a program calls a function, it must know how to return to its caller To make this possible, it pushes all the information it needs to remember onto a stack Return address Local variables and parameters This stack is known as the function call stack The information saved is known as the activation record or stack frame Every function call creates a new activation record Every time a function returns, its data is popped off the stack Call Stack for wash(3) ^ top 13.2.4: Developing a Recursive Algorithm Before we write recursive functions, we must develop a recursive algorithm To develop a recursive algorithm, we must find a way to do the following: Use a solution to a smaller or easier version of a problem to arrive at the solution itself Know when the problem is small enough to solve directly As another example of recursion, let us look at exponentiation We will limit ourselves to positive integers The mathematical notation for exponentiation is: xy A function prototype for exponentiation could be: int power(int x, int y); The definition of exponentiation is: xy = 1 * x * x * x ... (y times) Developing the Recursive Algorithm We start developing the algorithm by working through the process by hand It seems like a lot of work, and so we get someone else to do most of the work If we could get someone else to calculate xy - 1, we could just multiply by x xy = x * xy - 1 This process could repeat until we are done How do we know when we are done? Recursive Algorithm For Exponentiation If y is 0, we are done and the result is x0, which is 1 Else (while y ≥ 1): Ask someone else to compute xy - 1 We multiply the result of xy - 1 times x ^ top 13.2.5: Coding the Recursive Algorithm Implementing a recursive algorithm is usually straightforward Example Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> using namespace std; int power(int x, int y); int main() { int x, y; cout << "Enter x and y: "; cin >> x >> y; cout << power(x, y) << endl; } int power(int x, int y) { if (y == 0) { return 1; } else { int result = power(x, y - 1); return x * result; } } The Recursive Call Note how the power() function calls itself int power(int x, int y) { ... int result = power(x, y - 1); ... } Calling a function from within that function is a recursive call The arguments to the recursive call must define a task that is smaller or easier than the task given to the caller In this case, the caller must calculate xy But the recursive call is an easier task: xy - 1 Termination: I Won't be Back The power() function has a conditional return that does not involve a recursive call: int power(int x, int y) { if (y == 0) { return 1; ... } } The termination step is essential to any recursive procedure It checks to see if the task can be carried out without using recursion If so, it terminates the recursion by preventing any further recursive calls Note that the terminating condition must be checked before a recursive call Otherwise, the recursive call would go on indefinitely The terminating condition would never be reached ^ top 13.2.6: Tracing the Execution How does the recursive function actually work? We can trace the power(2, 3) called from main(): main() calls power(2, 3) power(2, 3) calls power(2, 2) power(2, 2) calls power(2, 1) power(2, 1) calls power(2, 0) power(2, 0) returns 1 (base case) power(2, 1) returns 2 power(2, 2) returns 4 power(2, 3) returns 8 power(2, 3) returns 8 to main() Note that the first half makes successive function calls Until the base case is reached Second half returns the values of the recursive case Instrumenting the Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> using namespace std; int power(int x, int y); int main() { int x, y; cout << "Enter x and y: "; cin >> x >> y; cout << "main() calls power(" << x << ", " << y << ")\n"; int result = power(x, y); cout << "power(" << x << ", " << y << ") returns " << result << " to main()\n"; } int power(int x, int y) { if (y == 0) { cout << "power(" << x << ", 0) returns 1 (base case)\n"; return 1; } else { cout << "power(" << x << ", " << y << ") " << "calls power(" << x << ", " << (y - 1) << ")\n"; int result = power(x, y - 1); cout << "power(" << x << ", " << y << ") returns " << (x * result) << endl; return x * result; } } ^ top 13.2.7: Using Recursion with Input Validation Recall our discussion of input validation in lesson 5.3.6 We can put this input validation code inside a function as shown below: double readNumber() { bool more = true; while (more) { cout << "Enter a number: "; double input = 0.0; cin >> input; if (cin.fail()) { cout << "Please enter numbers only!\n"; cin.clear(); cin.ignore(INT_MAX, '\n'); } else { more = false; } } return input; } To allow a user to reenter data we needed to use a loop like the one shown above The loop complicates the code We can simplify the code by using recursion instead: double readNumber() { cout << "Enter a number: "; double input = 0.0; cin >> input; if (cin.fail()) { cout << "Please enter numbers only!\n"; cin.clear(); cin.ignore(INT_MAX, '\n'); return readNumber(); } return input; } Notice how much shorter and simpler the code looks All we needed to repeat the input operation on error was one line: return readNumber(); Example of Input Validation with Recursion 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> using namespace std; // Recursive function to read a double double readNumber() { cout << "Enter a number: "; double input = 0.0; cin >> input; if (cin.fail()) { cout << "Please enter numbers only!\n"; cin.clear(); cin.ignore(INT_MAX, '\n'); return readNumber(); } return input; } // Main function for testing. int main() { double num = readNumber(); cout << "You entered: " << num << endl; return 0; } ^ top Exercise 13.2 In this exercise we look at several examples of recursion. Specifications Determine who your pair-programming partner is for this exercise. Work through each of the following recursive problems in order with two people working on one computer. Alternate the driver and navigator for each problem. Start by writing or typing the recursive algorithm and then implement the code. Make sure you discuss the solutions with your partner as you develop them together. Recursive Problems Write a function using recursion to print numbers from n to 0. Hint: Look at the code for the washing dishes example. Write a function using recursion to print numbers from 0 to n. Hint: You only need to move the output statement for the previous problem. Write a function using recursion named printStars() that receives a single int parameter and returns nothing. It the parameter value is greater than zero, the function prints to the console the given number of asterisks; otherwise it does nothing. For instance, calling printStars(8) displays: ******** (8 asterisks). Write a function using recursion that displays a string in reverse. Do not use arrays, loops or additional strings. Recall from lesson 3.2.5 that you can access part of a string using the substr() function. Also, you can determine the length of a string using the length() function. Also, you can use square bracket notation to access a single character as discussed in lesson 6.1.2. Also note that your recursive function will need two parameters: one for the string and one for the index of the string. Write a recursive function for summing the values between 1 and n, where n is any positive integer. Examples of summing: sum(1) = 1 sum(2) = 2 + 1 = 3 sum(3) = 3 + 2 + 1 = 6 sum(4) = 4 + 3 + 2 + 1 = 10 We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears for all the bunnies recursively without loops or multiplication or division. Example results of calling the bunnyEars() function: bunnyEars(0) -> 0 bunnyEars(1) -> 2 bunnyEars(2) -> 4 Hint: The bunnyEars() function needs to return the number of bunny ears. ^ top 13.2.8: Summary Recursion is when an algorithm is defined in terms of itself It allows us to define subproblems similar in form to the original Recursion always has two parts: Base case A problem that is closer to the solution Eventually, the base case is always called Without the base case, you would have infinite recursion More Information on Recursion If you still don't get it, See: "Recursion". Recursion: from Wikipedia ^ top Wrap Up Due Next: Sampler Project (5/27/10) When class is over, please shut down your computer if it is on Work on your project! ^ top Home | Blackboard | Day Schedule | Eve Schedule Syllabus | Help | FAQ's | HowTo's | Links Last Updated: May 19 2010 @15:38:08