13A: Recursion

What We Will Cover Announcements Continuations 13.1: Recursive Thinking 13.1.1: Recursive Definitions 13.1.2: Infinite Recursion 13.1.3: Recursion in Math 13.1.4: Summary Exercise 13.1 13.2: Recursive Programming 13.2.1: Writing Recursive Methods 13.2.2: Example: Sum 13.2.3: Tracing the Execution 13.2.4: Recursion vs. Iteration 13.2.5: Summary Exercise 13.2 13.3: Lecture Finale 13.3.1: What We Have Learned 13.3.2: End of Course Survey 13.3.3: About the Project Presentation Part 2 Wrap Up Assignments Due Next: Sampler Project (12/10/03) Continuations Questions on What's Due Next? Sampler Project (12/10/03) Questions from last class? ^ top 13.1: Recursive Thinking Objectives At the end of the lesson the student will be able to: Explain the underlying concepts of recursion Define infinite recursion and discuss how to avoid it "To understand recursion, one must first understand recursion." -- Unknown ^ top 13.1.1: Recursive Definitions Recursion: when an algorithm is defined in terms of itself. Recursion is a natural approach to some problems 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 For example, suppose we wanted to defined a list of numbers separated by commas We can define this list recursively as: A List is a: number or a: number comma List Examples of a List include: 10 21, 6, 54, 7, 19 10, 11, 15 No matter how long the list is, the recursive definition describes it List of one element, like the first example, is covered by the first rule Lists longer than one number are covered by the second rule Second rule is known as the recursive part Used as many times as needed until the last element is reached Last element is always defined by the non-recursive part, known as the base case ^ top 13.1.2: Infinite Recursion Note that the definition of a List has two parts One option is not recursive One option is recursive Recursion always divides the problem into two parts: Base case Simpler problem Simpler problem divides the problem again until solvable with the base case Must eventually terminate with the base case If only the recursive case was used, the definition would never end Known as infinite recursion Similar to infinite loops ^ top 13.1.3: Recursion in Math Math has many instances of recursion One classic example is n!, pronounced n-factorial The factorial n! is defined for a positive integer n as: When n = 0 n! = 1 And for values of n greater than 0: n! = n * (n-1) * (n-2) * (n-3) * ... * 1 For Example 3! is defined as: 3! = 3 * 2 * 1 = 6 5! is defined as: 5! = 5 * 4 * 3 * 2 * 1 = 120 Another Notation Another notation for the factorial definition is: N(x) = x * N(x - 1) N(0) = 1 Symbol x represents the current factorial number N(x) represents the accumulated value Further Information Factorial: from Mathworld Factorial: from Wikipedia ^ top 13.1.4: 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 ^ top Exercise 13.1 Use the next 5 minutes to complete the following exercises and answer any questions. We will discuss the questions after the time has elapsed. Exercises What is recursion? When is a base case necessary for recursive definitions? Write a recursive definition of i * j, when i > 0. Define the multiplication process in terms of integer addition. Examples of integer multiplication: 2 * 3 = 3 + 3 = 6 4 * 7 = 7 + 7 + 7 + 7 = 28 ^ top 13.2: Recursive Programming Objectives At the end of the lesson the student will be able to: Define recursive methods Trace the processing steps of recursive methods Explain when to use recursion and when to use iteration ^ top 13.2.1: Writing Recursive Methods Recursive methods implement recursive algorithms Methods call themselves either directly, or indirectly through another method General form of recursive methods: returnValue recursiveMethod(arguments) { If (stopping condition) { // base case /* do whatever at the end */; } else { //execute recursive step recursiveMethod(arguments); } } Recursive methods must eventually terminate Must have at least one base, or stopping, case. A base case does not execute a recursive call. Base case used to stop the recursion Each successive call to a method must be a "smaller version of itself" so that a base case is eventually reached ^ top 13.2.2: Example: Sum Consider the problem of summing the values between 1 and n Where n is any positive number We start our analysis by looking at a few examples: S(1) = 1 S(2) = 2 + 1 = 3 S(3) = 3 + 2 + 1 = 6 S(4) = 4 + 3 + 2 + 1 = 10 We can write a recursive definition to the problem S(x) = x + S(x - 1) S(1) = 1 Can convert the solution into a method named sum public class RecursiveSums { static int sum(int x) { int result; if (x == 1) result = 1; else result = x + sum(x - 1); return result; } public static void main(String[] args) { int sum4 = sum(4); System.out.println(sum4); } } Note how our definition is embodied in the sum method ^ top 13.2.3: Tracing the Execution How does the method actually work? Can trace the sum(4) called from main main() calls sum(4) sum(4) calls sum(3) sum(3) calls sum(2) sum(2) calls sum(1) sum(1) returns 1 sum(2) returns 3 sum(3) returns 6 sum(4) returns 10 main() assigns return value of 10 to sum4 Note that the first half makes successive method calls Until the base case is reached Second half returns the values of the recursive case ^ top 13.2.4: Recursion vs. Iteration All recursive algorithms or methods can be rewritten without recursion Methods rewritten without recursion usually have loops, so they are called iterative methods For example, we could write an iterative version of sum: static int sum(int x) { int result = 0; for (int i = 1; i <= x; i++) result += i; return result; } Iteration Uses repetition structures (for, while or do-while) Repetition through explicit use of repetition structure Terminates when loop-continuation condition fails Controls repetition by using a counter variable Recursion Uses selection structures (if, if-else or switch) Repetition through repeated method calls Terminates when base case is satisfied Controls repetition by dividing problems into simpler ones Choosing Recursion or Iteration Recursion has more overhead than iteration More memory used More processor steps taken Iterative methods generally run faster and use less memory space Recursion often shows the algorithm more clearly Can be implemented with only a few lines of code When should you use recursion? When efficiency is not important and it makes the code easier to understand ^ top 13.2.5 Summary Recursive methods implement recursive algorithms Methods call themselves either directly or indirectly through another method General form of recursive methods: returnValue recursiveMethod(arguments) { If (stopping condition) { // base case /* do whatever at the end */; } else { //execute recursive step recursiveMethod(arguments); } } All recursive methods can be rewritten without recursion Use iterative (looping) statements rather than recursive method calls Use recursion when efficiency is not important and it makes the code easier to understand Otherwise, use iteration ^ top Exercise 13.2 Use the next 5 minutes to complete the following. We will discuss the question after the time has elapsed. Write a program to solve i * j recursively. Use the definition we defined in the prior exercise. Submit your code with the exercises for this lesson. ^ top 13.3: Lecture Finale Objectives At the end of the lesson the student will be able to: Discuss the final preparation for the project presentation Advise the instructor on how to improve future courses ^ top 13.3.1: What We Have Learned During the course, we have learned how to: Compile source code into Java bytecode Run Java programs Declare classes and work with data types Use arithmetic expressions Declare and use variables to store data Display program output, both to the console and to a dialog Collect data from users using dialogs Use conditional statements to make our applications appear intelligent Use loops to repeat code Validate user input to verify our programs receive the proper type of data Write methods to group related code Use a professional coding style Create classes and objects Use inheritance to extend our classes and to enhance their functionality Design programs using classes and objects Use and throw exceptions Use arrays to group our data Perform common programming tasks on arrays Construct and process string data Use files and streams for program input and output Create and use interfaces Code graphical user interfaces (GUIs) Create Applets for use on the World-Wide Web Start thinking and programming recursively With this knowledge, you can create programs of moderate complexity Also, you have a solid foundation for more advanced programming Your sampler project will allow you to demonstrate what you have learned ^ top 13.3.2: End of Course Survey Please take a few minutes to answer this short survey This will help the instructor to improve future courses Survey respondent answers are anonymous The link to WebCT is here You may want to rate the textbook at your favorite book seller, such as: amazon.com Barnes & Noble.com ^ top 13.3.3: About the Project Presentation Before the Presentation Submit the following to WebCT before the presentation: README.txt file All source code files Any data files required Sampler Report Bring a written report on paper to give to the instructor If you submit a zip file, the file must extract into a directory that the instructor chooses. Please do NOT use absolute (full) paths. During the Presentation The presentation consists of the following information: A brief introduction describing the purpose of your application A demonstration of your sampler project A summary list of the functional specifications and a brief description of how you met these requirements in your project A list of any extra-credit features Point out the extras so we can all appreciate them Try to keep the presentation to 10 minutes or less After the Presentation Feel free to leave (or stay) after your presentation You can present to the instructor alone after the other presentations are through ^ top Part 1 Wrap Up Due Next Class: Sampler Project (12/10/03) ^ top Part 2: What We Will Cover Announcements Continuations 13.4: Final Exam Preparation 13.4.1: About the Final Exam 13.4.2: Recommended Preparation 13.4.3: Exam Taking Tips 13.4.4: End of Course Survey 13.5: Sampler Presentation 13.5.1: Sampler Presentation Wrap Up Assignments Due Next: Nothing ^ Part 2   ^ top Continuations Questions on Completed Assignment? Sampler Project (12/10/03) Questions from last class? ^ Part 2   ^ top 13.4: Final Exam Preparation Objectives At the end of the lesson the student will be able to: Discuss how to prepare for the final exam Describe how to take the final exam ^ Part 2   ^ top 13.4.1: About the Final Exam Important Exam Information Date and Time: 12/15/03 @ 7:00 A.M. to 9:50 A.M. Location: Room 516 (regular classroom) You must attend the exam or you will receive a score of zero (0) Except by prior arrangement with the instructor I am using WebCT to administer the test The exam is designed to take about 1.5 hours to complete However, you will have the full scheduled time to complete the exam You may have less time if you are late to the exam The exam is closed books and closed notes However, you may have one 3" x 5" card of notes for the exam You may use your computer for taking the exam in WebCT You may use the computer to compile or run programs You may NOT use the computer to use the Internet You may NOT communicate with your neighbor during the exam ^ Part 2   ^ top 13.4.2: Recommended Preparation Work through the Practice Final Exam questions Working the problems in groups is encouraged Get explanations for anything you do not understand Review your notes and prepare your 3" x 5" card Review the questions from the midterm exams Review your homework assignments and solutions Get plenty of rest before the exam ^ Part 2   ^ top 13.4.3: Exam Taking Tips Save after every answer -- you can always choose another answer If you get stuck on a question, make your best guess and return later If you are equally uncertain between two choices, go with first impression You do not need to comment code for tests and exams Unless specifically instructed to in the exam question Use the full time available More quiz tips: Basic Rules For Taking a Multiple-Choice Test ^ Part 2   ^ top 13.4.4: Questions and Answers Any questions? ^ Part 2   ^ top 13.5: Sampler Presentation Objectives At the end of the lesson the student will be able to: Present their sampler assignment ^ Part 2   ^ top 13.5.1: Sampler Presentation Before the Presentation Submit the following to WebCT before the presentation: README.txt file All source code (i.e. .java files) Any other source code needed to make your program function. Bring a written report on paper to give to the instructor If you submit a zip file, the file must extract into a directory that the instructor chooses. Please do NOT use absolute (full) paths. During the Presentation Present the following information: A brief introduction describing the purpose of your application A demonstration of your sampler project A summary list of the functional specifications and a brief description of how you met these requirements in your project A list of any extra-credit features Point out the extras so we can all appreciate them Try to keep the presentation to 10 minutes or less After the Presentation Feel free to leave (or stay) after your presentation You can present to the instructor alone after the other presentations are through ^ Part 2   ^ top Home | WebCT | Announcements | Schedule | Expectations | Syllabus Help | FAQ's | HowTo's | Links Last Updated: December 08 2003 @11:11:58