Test Review & Reteach [ 8.00 ] [ Todays Date ] [ Instructor Name ] Homework

Read HW 12.1 up to Structure of Recursive Solutions Correct any incorrect test answers by re-answering on a separate sheet of paper: To get back credit, you must justify your new answers.

Staple new answer sheet to the old test and return it tomorrow. Thinking Recursively [ 8.01 ] [ Todays Date ] [ Instructor Name ]

Tower of Hanoi Rules:

Move all of the rings to the right-most rod You can only take one ring at a time A ring cannot be put on a smaller ring

Discussion Iteration vs Recursion Iteration: A programming technique in which you describe actions to

be repeated typically using a loop. Recursion: A programming technique in which you describe actions to be repeated using a method that calls itself.

By Trixx - I designed this using http://thewalnut.io/, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=43282866 Homework Read the rest of HW 12.1

Writing Recursive Solutions [ 8.02 ] [ Todays Date ] [ Instructor Name ]

What makes a method recursive? How would we write a recursive method? In pseudocode or code if possible!

What makes a method recursive? Base case: A case within a recursive solution that is

so simple, it can solved without needing to call the method again. Recursive case: A case within a recursive solution that

involves reducing the overall problem to a simpler problem of the same kind that can be solved with a recursive call.

A recursive method: public static void writeStars (int x) { if (x == 0) { System.out.println();

} else { System.out.println(*); writeStars(x 1); }

} Wrong recursion: public static void writeStars(int x) {

System.out.print(*); writeStars(n - 1); } What is the output of this recursive call?

Grudgeball Slides reserved for your own or

chosen Grudgeball questions. Homework Read the rest of HW 12.2

Complete self-check questions %5, 7 9 and exercise #1 Mechanics of Recursion

[ 8.03 ] [ Todays Date ] [ Instructor Name ] Slide reserved for teacher demo, scratch MIT dragon curve, etc. Any way you think would best model recursion for your respective class.

The Lesson Plan has great examples and activities to choose from. Iterative to Recursive and Vice Versa Recursive

Iteration int factorial(int n){

if (n == 1){ int factorial(int n){ int product = 1;

return 1; for (int i = 2; i <= n; i++){

}else{ product *= i;

return n*factorial(n-1); } }

} return product;

} Iterative vs Recursive Recursion can be used to traverse String, array, and ArrayList objects,

much like a loop Any recursive solution could be written with iteration (loops) instead Some algorithms are easier to solve recursively, like traversing trees In general recursive solutions are more resource intensive than iteration

Koch Curve 1. Divide the line segment into three segments of equal length 2. Draw an equilateral triangle that has the middle segment from step

1 as its base and points outward 3. Remove the line segment that is the base of the triangle from step 2 4. Recur

Koch Visuals Koch Curve Zoom: https://www.youtube.com/watch?v=PKbwrzkupaU Mandelbrot Zoom: https://www.youtube.com/watch?v=0jGaio87u3A

Homework Complete self-check #6, 10, and exercise #3

Merge Sort [ 8.04 ] [ Todays Date ] [ Instructor Name ] Recursive Application

Now that we know recursion, we can do merge sort. Like selection and insertion sort, merge sort works on arrays. Merge sort worst case performance is O(n log n)

Merge sort in action: On paper, plan out all of the steps to merge sort.

Steps to merge sort: Split the array into two halves down to one element.

Sort the left half. Sort the right half Merge the two halves together.

Recursion The merge: Maintain a current index for each list starting at 0.

14 32

67 76

23 41

58 85

76 85

Create an empty list to hold the result. When we havent exhausted our two lists, insert the smallest element at the point and advance the index.

14 23

32 41

58 67

MergeSort The algorithm: If the lists size is 0 or 1, just return the original list (as it is stored).

Split the list parameter into two lists, of (roughly) equal size. Sort both split lists, list 1 and list 2. Merge the two sorted lists (list 1 and list 2), and return the result.

Homework Summarize notes for notebook check tomorrow. Finding and Fixing

Errors [ 8.05 ] [ Todays Date ] [ Instructor Name ] Todays plan:

Error check and resubmit all chapter 12 assignments. Study for the test by: Reviewing all of the blue, self-check pages at the end of Chapter 9. Re-reading sections as needed to complete the self-check problems.

Homework Regrade/Resubmit You all have the opportunity to get full credit on your homework grades by correcting them now, in class.

Use your error checking algorithm, and if you need help just ask! Homework Begin reviewing chapter 12 for the quiz.

Review and Quiz [ 8.06/7 ] [ Todays Date ] [ Instructor Name ]

Whats on the test? Review Topics Make a list of review topics that you feel you need to go over for the

test tomorrow. For each topic, follow up by reviewing the textbook, self-check problems, and the appropriate Practice problems.

Quiz Good Luck!