13: Recursion and Other Topics

What We Will Cover Announcements Continuations 13.1: Introduction to Recursion 13.1.1: About Recursion 13.1.2: Implementing Recursive Functions 13.1.3: How Recursion Works 13.1.4: Developing a Recursive Algorithm 13.1.5: Coding the Recursive Algorithm 13.1.6: Tracing the Execution 13.1.7: Summary Exercise 13.1 13.2: Running Under Windows 13.2.1: About DLL's 13.2.2: Finding the DLL's You Need 13.2.3: Summary Exercise 13.2 13.3: A Taste of GUI Programming 13.3.1: About Graphical User Interfaces (GUIs) 13.3.2: Windows APIs 13.3.3: Windows API Programming Example Exercise 13.3 Wrap Up Due Next: Sampler Project (5/24/07) Continuations Questions from last class? Questions on What's Due Next? Sampler Project (5/24/07) What to take next? Schedule of Classes After completing CS-11 you are qualified to take either CS-19 or cs-20J CS-19: C++ programming and software design methodologies CS-20J: Java programming and software design methodologies Each course has a initial review section such that you could learn the syntax with a little effort Other computer-related courses on which you can use your programming skills CIS 132: Introduction to Internet Programming ^ top 13.1: Introduction to Recursion Objectives 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 "To understand recursion, one must first understand recursion." -- Unknown ^ top 13.1.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 For 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.1.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.1.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.1.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.1.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.1.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.1.7: 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 Recursion: from Wikipedia ^ top Exercise 13.1 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 that displays a string in reverse. Do not use arrays or additional strings. Recall that you can access any character of a string using square brackets ([]) or the at() function. Also, you can determine the length of a string using the length() function. For example: cout << myString.length(); cout << myString[index]; 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 One possible solution ^ top 13.2: Running Under Windows Objectives At the end of the lesson the student will be able to: Run console programs under Windows ^ top 13.2.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.2.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() { char answer = 'y'; while (answer == 'y') { cout << "\nPlaying an exciting game!\n"; cout << "Do you want to play again? (y/n) "; cin >> answer; } cout << "\nThanks for playing!\n"; return 0; } ^ top 13.2.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 Exercise 13.2 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 Cygwin window (command line window) and 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.3: A Taste of GUI Programming Objectives At the end of the lesson the student will be able to: Compile and run a simple GUI program ^ top 13.3.1: About Graphical User Interfaces (GUIs) Graphical User Interface (GUI) -- pronounced "gooey" Graphical: not just text or characters but includes windows, menus, buttons, etc. User: person using the program via mouse, keyboard, etc. Interface: interaction with the program using visual controls, widgets, etc. Most modern programs use a GUI Typical graphical elements include: Window: portion of screen that serves as a smaller screen within the screen Menu: list of alternatives offered to user Button: looks like a button that can be pressed Objects that make up a GUI are called components or widgets ^ top 13.3.2: Windows APIs To implement a GUI using C++, you must first decide on a GUI library The most commonly used library is the Windows API (application programming interface) An API provides a set of functions as an interface to a software library Win16 was the first, 16-bit version of these APIs. Win32 is the modern version in widespread use Win64 is a 64-bit extension of Win32 The Win32 API consists of C functions implemented in dynamically linked libraries (DLLs) The key DLLs are: kernel32.dll user32.dll gdi32.dll You can find these DLLs in the C:\WINDOWS\system32 directory Cygwin allows you to build programs with full access to the standard Win32 API Including GUI functions More Information GUI Mode Applications: from the Cygwin User's Guide Windows API: from Wikipedia ^ top 13.3.3: Windows API Programming Example Follow the link is a "simple" Windows API program from Reliable Software See the Windows API Tutorial It creates a window titled "Hello Windows!" The program consists of two files shown below You can use TextPad to compile and run the program Also, you can compile the application, use the standard g++ command: g++ -o hellogui winnie.cpp To run it, type: ./hellogui Example File: Winnie.h Example File: Winnie.cpp Further Information See the Windows API Tutorial: a good place to start learning the Windows API Programming Windows with MFC: a great resource for Win32 API programmers Frequently Asked Questions about Win32 Programming ^ top Exercise 13.3 Compile and run the Winnie program. ^ top Wrap Up Reminders Due Next: Sampler Project (5/24/07) When class is over, please shut down your computer There is no need to turn in this weeks exercises ^ top Home | Blackboard | Announcements | Day Schedule | Eve Schedule Course info | Help | FAQ's | HowTo's | Links Last Updated: May 17 2007 @17:09:29