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: Developing a Recursive Algorithm 13.1.4: Coding the Recursive Algorithm 13.1.5: Tracing the Execution 13.1.6: 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: Exercise 11 (12/1/05) Sampler Project (12/8/05) Continuations Questions on What's Due Next? Exercise 11 (12/1/05) Sampler Project (12/8/05) Questions from last class? ^ 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 function 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 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 set of dishes and then ask someone else to wash the dishes This sequence repeats until all the dishes are washed 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 contains a reference to 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 Recursion is an easy and powerful way of tackling many difficult computing problems You implement recursion using functions that call themselves Like a loop, a recursive function must have some way to end Usually the base case is written first and the recursive step second Recursive Function Structure 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); } } 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: Developing 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 y 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.4: 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.5: 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 method 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.6: Summary Recursion is when an algorithm is defined in terms of itself Allows us to define subproblems in similar 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. You should be able to work out the solutions to the following problems. Recursive Problems What is wrong with the following recursive definition? For the definition of recursion, see recursion :) Write a function using recursion to print numbers from n to 0. Write a function using recursion to print numbers from 0 to n. (You only need to shift one line in the program of the previous problem.) Write a function using recursion to enter and display a string in reverse. Do not use arrays or additional strings. Write a function using recursion to enter and display a string in reverse and state whether the string contains any spaces. Do not use arrays or additional strings. 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. Choose an application, compile it and copy the exe file to the desktop Run the file and find the missing DLL's Add the missing DLL's 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: form 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 Tutorials 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 Tutorials: 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: Exercise 11 (12/1/05) Sampler Project (12/8/05) When class is over, please shut down your computer There is no need to turn in this weeks exercises ^ top Home | WebCT | Announcements | Day Schedule | Eve Schedule Course info | Help | FAQ's | HowTo's | Links Last Updated: November 29 2005 @18:17:02