Building Java Programs

Building Java Programs

Building Java Programs Chapter 12 introduction to recursion reading: 12.1 2 Road Map - Quarter CS Concepts Client/Implementer Efficiency

Recursion Regular Expressions Grammars Sorting Backtracking Hashing Huffman Compression Data Structures Lists Stacks Queues Sets Maps Priority Queues

Java Language Exceptions Interfaces References Comparable Generics Inheritance/Polymorphism Abstract Classes Java Collections

Arrays ArrayList LinkedList Stack TreeSet / TreeMap HashSet / HashMap PriorityQueue 3 Road Map - Week Monday Introduce idea of recursion Goal: Understand idea of recursion and read recursive code. Tuesday Practice reading recursive code

Wednesday More complex recursive examples Goal: Identify recursive structure in problem and write recursive code Thursday Practice writing recursive code Friday Exam logistics Set-up for A5 4 Recursion recursion: The definition of an operation in terms of itself. Solving a problem using recursion depends on solving smaller occurrences of the same problem. recursive programming: Writing methods that call themselves to solve problems recursively. An equally powerful substitute for iteration (loops)

Particularly well-suited to solving certain types of problems 8 9 Getting down stairs Need to know two things: Getting down one stair Recognizing the bottom Most code will look like: if (simplest case) { compute and return solution } else { divide into similar subproblem(s) solve each subproblem recursively assemble the overall solution } 11 Recursion and cases

Every recursive algorithm involves at least 2 cases: base case: A simple occurrence that can be answered directly. recursive case: A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurrences of the same problem. Some recursive algorithms have more than one base or recursive case, but all have at least one of each. A crucial part of recursive programming is identifying these cases. 12 Recursion vs Iteration public static void writeStars(int n) { while (n > 0) { System.out.print("*"); n--; } System.out.println(); }

public static void writeStars(int n) { if (n == 0) { System.out.println(); } else { System.out.print("*"); writeStars(n 1); } } 23 Recursion vs Iteration public static void writeStars(int n) { while (n > 0) { System.out.print("*"); n--; } System.out.println(); // base case. assert: n == 0 } public static void writeStars(int n) { if (n == 0) { System.out.println(); // base case } else {

System.out.print("*"); writeStars(n 1); } } 24 Recursion vs Iteration public static void writeStars(int n) { while (n > 0) { // "recursive" case System.out.print("*"); // small piece of problem n--; } System.out.println(); } public static void writeStars(int n) { if (n == 0) { System.out.println(); } else { // "recursive" case. assert: n > 0 System.out.print("*"); // small piece of problem writeStars(n 1); } }

25 Recursion vs Iteration public static void writeStars(int n) { while (n > 0) { // "recursive" case System.out.print("*"); n--; // make the problem smaller } System.out.println(); } public static void writeStars(int n) { if (n == 0) { System.out.println(); } else { // "recursive" case. assert: n > 0 System.out.print("*"); writeStars(n 1); // make the problem smaller } } 26 Exercise Note: We did reverseDeck in lecture but they are the exact

same problem Write a recursive method reverseLines that accepts a file Scanner and prints the lines of the file in reverse order. Example input file: Expected console output: I have eaten the icebox the plums that were in that were in the plums the icebox I have eaten What are the cases to consider? How can we solve a small part of the problem at a time? 31

Tracing our algorithm call stack: The method invocations currently running reverseLines(new Scanner("poem.txt")); public static void reverseLines(Scanner input) { if (input.hasNextLine()) { String line = input.nextLine(); // "I have eaten" public static void reverseLines(Scanner input) { reverseLines(input); if (input.hasNextLine()) { System.out.println(line); String line = input.nextLine(); // "the plums" } static public void reverseLines(Scanner input) { reverseLines(input); } if (input.hasNextLine()) { System.out.println(line);

String line = input.nextLine(); // "that were in" } static public void reverseLines(Scanner input) { reverseLines(input); } if (input.hasNextLine()) { System.out.println(line); String line = input.nextLine(); // "the icebox" } static public void reverseLines(Scanner input) { reverseLines(input); } if (input.hasNextLine()) { // false System.out.println(line); ... } } file:

} input output: } I have eaten the icebox the plums that were in that were in the plums the icebox I have eaten 34

Recently Viewed Presentations

  • Ancient Rome BCE-CE De nobis fabula narratur

    Ancient Rome BCE-CE De nobis fabula narratur

    Spirits could be found in inanimate objects such as stones, rivers, furniture, and even caves. Children were told horrifying stories of monsters who would come to kill them if they misbehaved. Herbs could do many good things. (i.e.-they "made enemies...
  • Unit 6 Describing data - Home - SCCPSS

    Unit 6 Describing data - Home - SCCPSS

    Two-frequency tables. Recall: converting fractions into decimals, To convert fractions into decimals, Divide the Numerator (the number on top) by the denominator (the number on the bottom.) Example: 6/24. 6÷24=0.25 So the answer is 0.25. Recall: converting decimals to percents,...
  • Accommodations and Supports Student Data Profile Parental Input:

    Accommodations and Supports Student Data Profile Parental Input:

    Student Data Profile. Parental Input:. Karen's father participated by telephone in the parent-teacher conference. He was happy with her grades last year, but concerned about the amount of time it takes Karen to complete her homework assignments most nights.
  • The End of Stuff? Trajectory Trends Breakfast 27th

    The End of Stuff? Trajectory Trends Breakfast 27th

    pickles, chocolate, mayonnaise, cutlery. and . light." - John Peder Zane, 2013. Forms of Capital. Economic. Social. Cultural. Source: Bourdieu, 1986. Related both to the notions of the experience economy, and the notion floated by Steve Howard of Western society...
  • Whether China Should Accelerate Capital Account ...

    Whether China Should Accelerate Capital Account ...

    REER of RMB 38353 38384 38412 38443 38473 38504 38534 38565 38596 38626 38657 38687 38718 38749 ... NEER of RMB 38353 38384 38412 38443 38473 38504 38534 38565 38596 38626 38657 38687 38718 38749 ... If Chinese government accelerate...
  • Español 1 - lección preliminar

    Español 1 - lección preliminar

    Tú vs. Usted. In Spanish, there are multiple ways to say "you". You have to use the correct "you" depending on what you want to express. Let's take a look at the friendly and formal "you". Tú - this "you"...
  • Click to edit Master text styles Core Documents

    Click to edit Master text styles Core Documents

    Common problem areas or missing elements. And will also complete activities that will serve to: Deepen your understanding of the required elements. ... Operating in an ethical manner is a fundamental part of being a museum and fulfilling the public...
  • Thread Block Compaction for Efficient SIMT Control Flow

    Thread Block Compaction for Efficient SIMT Control Flow

    Identified DWF Pathologies. Greedy Warp Scheduling Starvation. Lower SIMD Efficiency. Breaks up coalesced memory access. Lower memory efficiency. Some CUDA apps require lockstep execution of static warps . DWF breaks them! Additional HW to fix these issues?