Skip to content

Latest commit

 

History

History
451 lines (380 loc) · 15.1 KB

T208-27112018.md

File metadata and controls

451 lines (380 loc) · 15.1 KB

LESSON 08 - TOPIC 2: Input/Output, Implementation Techniques, and Recursion

Accompanying code files:

  • N/A

Jump to Homework

Input/Output and Comments

A brief recollection of comments:

  • Comments should be used for procedural abstraction: Ensure that every method implemented has a corresponding conceptual description separate from implementation.
// This is a short comment in Java. It does not get compiled/executed.
// Remember that for each method you write, include a long comment at the top of it as below:

/** What the method is supposed to do, summarized in under 15 words.
 * @param param_name is the identifier of the parameter for this method. Including this gets the compiler to check that param_name is actually referred to in the method header and is referred to in the method body.
 * @return state what the method returns. This will get the compiler to check that a return statement is actually used in the method body, and that it returns something of the right type based on the method header.
 * See the example below
*/

/** Returns the area of a rectangle with specified length and width.
 *  @param length is the length of the rectangle
 *  @return the area of the rectangle
 */
 public double area(double length, double width)

Input

  • The truth is that there are a multitude of ways to provide user input to a program, but you are not required to know how any of them work for the AP exam.
  • If reading input is a necessary part of a question on the exam, it will exist as pseudocode, as below:
double x = call to a method that reads a floating-point number
double x = ...; // read user input

Output

  • There are multiple ways to provide output as well, but for the exam, it is restricted to using System.out.print and System.out.println (formatted output is not tested)
  • Notice that System.out is a method from the System class, and it allows output to be displayed on the console.
  • Try copying and pasting the output into a java class below and running it!
public void main(String[] args) {
  System.out.println("Hello World.");
  System.out.print("Goodbye");
  System.out.print("World");
}

Implementation Techniques

Top-Down Approach

  • a.k.a. stepwise design. Start with the big picture.
  • Involves breaking down a system into its compositional sub-systems in a reverse-engineering fashion
  • A brief overview of the system is formulated, but its first-level systems are not detailed or specified
  • Each subsystem is further refined in greater detail, until it is reduced to base elements
  • Useful approach for recursion and often used with black-box testing, and enables code reuse
  • Emphasizes thorough understanding before any coding begins, but delays testing as a result

Bottom-Up Approach

  • a.k.a. seed model
  • This involves piecing together smaller systems to produce more complex ones
  • A divergent (rather than convergent) approach, often used for information processing and modeling, but can result in uncoordinated systems
  • Supports early coding and testing

Object-Oriented Approach

  • Abstracting components of a system into digital 'objects' with state, behaviour, and relationships with other objects

Encapsulation and Information Hiding

  • Bundling data and methods related to specific objects within one unit, e.g. a class in Java
  • Good practice to avoid creating bugs (especially for big programs where you run out of names for all the different methods)

Recursion

  • A recursive method is a method that calls itself. Why would it do that?
  • It is similar to iteration in that it repeats instructions, but it does it in a self-similar way.
  • It makes use of the call stack in program execution, and as a result, uses more memory than an iterative method.
public class WordPlay {

  public static void stackWords() {
    String word = ...; // read user input
    if (word.equals("."))
      System.out.println();
    else
      stackWords();
    System.out.println(word);
  }

  public static void main(String args[]) {
    System.out.println("Enter list of words, one per line.");
    System.out.println("Final word should be a period (.)");
    stackWords();
  }

}
  • If you enter hold my hand ., the list gets printed in reverse: . hand my hold. Why?
  • Each time you make a recursive call to stackWords(), execution goes back to the start of the method, meaning that the System.out.println(word); line is not reached yet, and will only be reached once the call to stackWords() completes, resulting in word only being printed until the final recursive call to stackWords() made is completed.
  • This means that for the above input, you create 4 different calls to stackWords(), and the computer must remember to complete all the pending calls to the method.
  • It does this by stacking the print statements as below:
Call Stack
System.out.println("hand");
System.out.println("my");
System.out.println("hold");
  • It is called a call stack due to the first in, last out (FILO) order (like a stack of dishes).
  • Memory in the computer is segmented into different parts, one part for storing all the object/variable/method declarations, another part for executing the statements, and so on.
  • If the memory limit for the call stack is reached, e.g. due to an infinite recursion, a StackOverflowError occurs. Note that this is an error, not an exception, and thus your program will crash if this occurs.

General Form of Simple Recursive Methods Every recursive method has 2 distinct parts:

  • The base case or termination condition that causes the method to end
  • The nonbase case or reduction step that moves the algorithm towards the base case (termination)

If either are missing, the recursive statement will result in an infinite loop.

public void recursiveMethod(...) {
  if (base_case) {
    return something that terminates method
  } else {
    // perform something that leads a step closer to termination
    return recursiveMethod(...); // recursive method call
  }
}
  • The base case should be the simplest case for the problem (e.g. if an integer has the value of 0 or 1)
  • A method that has no pending statements following the recursive call is tail-recursive

For the AP Exam, you are not required to WRITE recursive methods, but you will need to be able to UNDERSTAND and HAND-TRACE them.

EXAMPLE: The Factorial Recursive Method A commonly used example to demonstrate recursion is the factorial method. Recall that factorials work like this: 4! = 4 * 3 * 2 * 1 = 24. This method can be implemented both iteratively and recursively. The iterative way is shown below:

public static int factorial(int n) {
  factorial = 1
  for (int i = 1; i <= n; i++) {
    factorial *= i;
  }
  return factorial;
}

How would we frame this recursively? Take a look at the table below:

n! defined iteratively n! defined recursively
0! = 1 0! = 1
1! = 1 1! = 1(0!)
2! = 2 * 1 2! = 2(1!)
3! = 3 * 2 * 1 3! = 3(2!)

If you notice with the iterative version, the factorial of the number, n, can use the factorial of the previous number, n-1, in its computation: n! = n * (n - 1)!. Thus, the general recursive definition for n! is:

  • Base Case: n! = 1 (n = 0)
  • Reduction Step: n(n-1)! (n > 0)

The implementation of the recursive version is thus:

public static int factorial(int n) {
  if (n == 0) {
    return 1; // base case
  } else {
    return n * factorial(n-1); // reduction step
  }
}

How would we hand-trace (evaluate the value of each recursive call) this recursive function? Go in an ascending order, starting with the base case on top, and working your way down until you reach the input number. Since the input (first) number is on the bottom and the base case (last number) is on the top, it resembles a stack:

Factorial(5) Hand-Trace
factorial(1) = 1
factorial(2) = 2 * factorial(1) = 2 * 1 = 2
factorial(3) = 3 * factorial(2) = 3 * 2 = 6
factorial(4) = 4 * factorial(3) = 4 * 6 = 24
factorial(5) = 5 * factorial(4) = 5 * 24 = 120
  • Conclusion: factorial(5) = 120

EXAMPLE: The Fibonacci Recursive Method Let's revisit the Fibonacci Sequence. This can also be implemented both iteratively and recursively. The general recursive definition for the Fibonacci Sequence is:

  • Base Case: 1 (n = 1,2)
  • Reduction Step: Fib(n - 1) + Fib(n - 2) (n >= 3)
// iterative version
public static int fibonacci(int n) {
  if (n <= 1) {
    return n;
  }

  int fib = 1;
  int prev_fib = 1;

  for (int i = 2; i < n; i++) {
    int temp = fib;
    fib += prev_fib;
    prev_fib = temp;
  }
  return fib;
}

// recursive version
public static int fibonacci(int n) {
  if (n == 1 || n == 2) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}
Fibonacci(5) Hand-Trace
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3
fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5
  • Conclusion: fibonacci(5) = 5

Notice that with the Fibonacci method, the recursive version actually looks simpler and in fact, suits it better. This is because it has a natural binary tree structure, where each call to the Fibonacci method results in two more recursive calls to the Fibonacci method, as show below:

image

General Rules for Recursion

  1. Avoid recursion for algorithms that involve large local arrays. Too many recursive calls can cause memory overflow.
  2. Use recursion when it significantly simplifies code.
  3. Avoid recursion for simple iterative methods (e.g. factorial, Fibonacci, and linear search)
  4. Recursion is especially useful for branching processes (e.g. traversing trees) or directories, and divide-and-conquer algorithms like merge sort and binary search.

We did the following questions in class (Use tables to keep track of values when approaching these questions, and don't forget to refer to the AP Exam Quick Reference!):

  1. Consider the following recursive method:
public int puzzle(int num) {
  if (num <= 1)
    return 1;
  else
    return num + puzzle(num / 2);
}

What value is returned when puzzle(10) is called?

  • (A) 18
  • (B) 15
  • (C) 11
  • (D) 1
  • (E) Nothing is returned. Infinite recursion causes a stack overflow error.
  1. Consider the following recursive method:
public int mystery(int k) {
  if (k == 0)
    return 1;
  else
    return 2 * k + mystery(k - 2);
}

What value is returned when mystery(11) is called?

  • (A) 1
  • (B) 49
  • (C) 73
  • (D) 665280
  • (E) Nothing is returned. Infinite recursion causes a stack overflow error.
  1. Consider the following recursive method:
public int enigma(int n) {
  if (n < 3)
    return 2;
  if (n < 5)
    return 2 + enigma(n - 1);
  return 3 + enigma(n - 2);
}

What value is returned when enigma(9) is called?

  • (A) 7
  • (B) 10
  • (C) 13
  • (D) 15
  • (E) 16
  1. Consider the following recursive method:
public void printStars(int n) {
  if (n == 1) {
    System.out.println("*");
  } else {
    System.out.print("*");
    printStars(n - 1);
  }
}

What will be printed when printStars(15) is called?

  • (A) ***************
  • (B) *
  • (C) Nothing is printed. Method will not compile. Recursive methods cannot print.
  • (D) Nothing is printed. Method returns successfully.
  • (E) Many stars are printed. Infinite recursion causes a stack overflow error.
  1. Consider the following recursive method:
public String weird(String s) {
  if (s.length() >= 10)
    return s;
  return weird(s + s.substring(s.indexOf("lo")));
}

What will be printed when weird("Hello") is called?

  • (A) "Hello"
  • (B) "Hellolo"
  • (C) "Hellolololo"
  • (D) "Hellolololololololo"
  • (E) Nothing is returned. Infinite recursion causes a stack overflow error.

Questions 6-7 refer to the following methods:

public int factors(int number) {
  return factors(number, number - 1, 0);
}
public int factors(int number, int check, int count) {
  if (number % check == 0)
    count++;
  check--;
  if (check == 1)
    return count;
  return factors(number, check, count);
}
  1. What value is returned when factors(10) is called?
  • (A) 0
  • (B) 1
  • (C) 2
  • (D) 3
  • (E) 4
  1. Which of the following statements will execute successfully? I. int answer = factors(0); II. int answer = factors(2); III. int answer = factors (12, 2, 5);
  • (A) I only
  • (B) II only
  • (C) III only
  • (D) I and II only
  • (E) I, II, and III
  1. Consider the following recursive method:
public int function(int x, int y) {
  if (x <= y)
    return x + y;
  else
    return function(x - y, y + 1) + 2;
}
  • (A) 13
  • (B) 21
  • (C) 25
  • (D) 27
  • (E) Nothing is returned. Infinite recursion causes a stack overflow error.
  1. Consider this recursive problem: If you add up the digits of a number and get a sum of 9, then that number is divisible by 9, but if your answer is less than 9, then it is not divisible by 9. E.g.
  • 81 -> 8 + 1 = 9, divisible by 9
  • 71 -> 7 + 1 = 8, not divisible by 9 However, if you add up the digits of a big number, you get a sum that is greater than 9, e.g. 999 -> 9 + 9 + 9 = 27. We can fix this by doing the same thing to that result: 27 -> 2 + 7 = 9, divisible by 9. Consider the class below that implements this:
public class Div9 {
  public boolean divisible(int dividend) {
    return sumUp(dividend) == 9;
  }

  public int sumUp(int dividend) {
    int sum = 0;

    while (dividend > 0) {
      sum += dividend % 10;
      dividend = dividend / 10;
    }

    if (/* condition */)
      return sum;
    else
      return sumUp(/* argument */);
  }
}

Which of the following can be used to replace /* condition */ and /* argument */ so that sumUp will work as intended?

Option condition argument
(A) sum <= 9 sum
(B) sum = 9 dividend
(C) sum <= 9 dividend
(D) sum < 9 sum
(E) sum < 9 dividend / sum
  1. Imagine that the length() or size() functions to get the length of an array or list (or other sort of collection) did not exist, and you wanted to implement one on your own in a recursive way. What would be the base case and what would be the non-base case?

ANSWERS

  1. A
  2. E
  3. C
  4. A
  5. C
  6. C
  7. C
  8. B
  9. A
  10. If the end of an array or list is reached, there should be nothing (i.e. null) in its next slot.
  • Base Case: Next item = null (this.next == null)
  • Non-Base Case: Get length of rest of the list (this.next.length()) Implementation you never asked for:
public int length() {
  if (this.next == null)
    return 0;
  else
    return 1 + this.next.length();
}

HOMEWORK

Assignments:

  • Complete the remaining questions from the Introductory Java Language Features Question Set.
  • Complete the Recursion Question Set.
  • Answers will be posted on the Topic 2 assignment answers issue.

Prep for Next Class:

  • N/A