Introduction

This resource is presented as list of topics, functions, and patterns that we’ve encountered so far in CIS 110. It is reference material, and not a definitive textbook.

Please note that this resource is not…

• a comprehensive list of all information that might be tested on an exam
• a replacement for having viewed the live & recorded material that covered these topics
• an indication that something not covered here is not an important concept in learning programming & Java.
• an example of exactly the level of detail at which you need to understand a concept.

Here are a handful of good ways to use this document:

• As a starting point for preparing for an exam.
• As a way to check your understanding of a recent topic.
• As a reference for completing homeworks, especially when you recall that we’ve covered something similar to the problem at hand before in the class.
• As a way to double check why the code you’re writing isn’t compiling, or to remind you of some syntax rules that just won’t stick in your head.

You might notice that some text looks like this. When something is written in this way, it’s information that you might be interested to learn but that you’re not required to know.

Note: We leave the table of contents in full, but will not fill in the relevant information until it has been taught in lecture.

Table of Contents:

• Introduction
• Incomplete List of Functions & Operations We Have Used
• Basics of a Java Program
  • Writing & Running Code
  • The main Method & args
  • Code Blocks
• Drawing
• Variables
  • What A Variable Is
  • Declaring a Variable
  • Assigning a Value to a Variable
  • Variable Scopes
• Data Types
  • What a Data Type Is
  • Primitive Data Types in Java
    • Table of Primitives
    • Strings
  • Some Important Operators & Tools
    • Relational Operators
    • The multifaceted +
    • Mod (%)
    • Casting
    • Parsing
    • Math
• Conditionals
  • When to use a Conditional
  • if, else if, and else
  • Switch Statements
• Loops
  • Rules of Iteration in Java
  • The While Loop
  • The For Loop
  • Your Loop of Choice
  • Break and Continue
• Arrays
  • What is an Array?
    • Arrays Are Fixed-Length
    • Arrays Are Indexed
    • Arrays Contain Values Of One Type Only
  • Manipulating Arrays
    • Initializing entries of an array to random values
    • Printing the values of an array
    • Finding the maximum value in an array
    • Finding the sum & mean of an array of doubles
• Functions
  • Anatomy of a Function
  • Functions and Control Flow
  • Functions and Variable Scope
• Recursion
  • Essential Components of a Recursive Algorithm
  • Tracing Recursion
• Unit Testing
  • Essentials of a Test Case
  • Anatomy of a JUnit Test File
  • Passing and Failing Tests

Incomplete List of Functions & Operations We Have Used

• Basic operations:
  • Arithmetic
    • +, -, *, / on numeric types
    • %, the mod operator for numeric types
  • Logical
    • &&, || for booleans
  • Relational
    • ==, != for all primitive data types
    • <, >, <=, => for numeric primitive types
• Math operations
  • Math.pow for exponentiation (don’t use for squaring, though!)
  • Math.sqrt for square roots
  • Math.abs for absolute values
  • Math.min, Math.max for finding the smaller/larger of two values
• PennDraw functions
  • These are numerous, so review our PennDraw guide for the full listing
  • PennDraw.setPenColor, PennDraw.setPenRadius for changing drawing properties
  • PennDraw.clear to clear the screen, draw backgrounds
  • PennDraw.setScale, PennDraw.setXScale, PennDraw.setYScale for changing drawing scales.
  • Shapes range from simple (PennDraw.point) to complex (PennDraw.polygon)
  • PennDraw.enableAnimation and PennDraw.advance are essential for animation
  • Interactivity:
    • PennDraw.mousePressed, PennDraw.mouseX, and PennDraw.mouseY for mouse inputs
    • PennDraw.hasNextKeyTyped and PennDraw.nextKeyTyped for keyboard inputs
• Reading inputs with In
  • isEmpty for checking if there is anything left to read in the file
  • readInt, readDouble, readBoolean, readString, readLine all read & parse the next single value in the file as the desired data type. These all read one value at a time.
  • readAll consumes the rest of the text in the file and returns it to you as a (potentially very long) String.
• Printing
  • System.out.println prints its input, followed by a line break (an '\n' character).
  • System.out.print prints its input exactly, with no space add afterwards.
• Arrays
  • arr.length evaluates to the length of the array arr as an int.
  • arr[i] evaluates to the value stored at index i within array arr.
• Strings
  • + is used for concatenating a value with a String. More on this here.
  • s.length() returns the length of the String as an int.
  • s.charAt(i) returns the char at index i in String s.
  • s.toUpperCase() and s.toLowerCase() return a new String with all alphabetic chars in s converted to uppercase and lowercase, respectively.

Basics of a Java Program

Writing & Running Code

• Java code is written in .java files.
• Code must be compiled before it can be run.
  • To compile your code, press the “Compile” button on the top bar in Codio.
  • Every time you change your code, you must re-compile your code before running it so that the changes are executed.
• To run a Java program that has been compiled, you must meet several important criteria. If the program is ExampleFile.java, then the layout of the program must match the following:

  // This file is named ExampleFile.java
  public class ExampleFile {
      // Other code & functions can come before or after main, too
      public static void main(String[] args) {
          ...
      }
      // Other code & functions can come before or after main, too
  }
  

  • Specifically, the name of the file and the top-level class name must match.
  • Additionally, the program needs a main function to be run directly.
• A program, once compiled, can be run with java ExampleFile from the Codio terminal, optionally passing in command line arguments as well.

The main Method & args

This is the entry point to a program. That is, when you run java Apples fuji macintosh pink-lady, you’re doing the following:

• Java finds the method defined as public static void main(String[] args) from Apples.java
• The execution of the program starts at the beginning of the main method, and continues until main returns, including any potential method calls in main.
• The input argument to main called args is an array of Strings representing the list of arguments passed in from the run command. In this case, args would be equal to {"fuji", "macintosh", "pink-lady"}
  • args is always an array of Strings. If you intend to interpret the input as numbers, you’ll need to use parsing on the relevant members of args (Integer.parseInt(s), Double.parseDouble(s)).

Code Blocks

Java programs are essentially sequences of nested code blocks. Code blocks are groups of lines of code that live between an open brace (this character: { ) and its corresponding close brace (this character: }). Note that a block of code does not necessarily end at the first } character following a { character in the case of nested code.
An illustration follows, with each comment specifying which code block that line would belong to. Note the fact that code blocks can nest, and how this is represented here with the decimal notation (block 1.2.1 is the first block inside the second block inside the first block, for example).

public class CodeBlockExample {
  // BLOCK 1
  public static void main(String[] args) {
    // BLOCK 1.1
    for (...) {
      // BLOCK 1.1.1
    }
    // BLOCK 1.1
    while (...) {
      // BLOCK 1.1.2
    }
    // BLOCK 1.1
  }
  // BLOCK 1

  public static int tester() {
    // BLOCK 1.2
    for (...) {
      // BLOCK 1.2.1
    }
    return 0; // BLOCK 1.2
    // BLOCK 1.2
  }
}

Drawing

A complete reference to drawing with PennDraw is already available on the course site. Some key points:

• The default coordinate system for PennDraw canvases has (0, 0) in the bottom left corner and (1, 1) at the top right corner. You can use PennDraw.setScale() to change this as makes sense to your program.
• All shapes (from points to polygons) are drawn to the color specified by the PennDraw penColor. To change the color of a shape, you must add a call to PennDraw.setPenColor() at some point before the line where you draw the shape.
• Animation is disabled by default.
  • A call to PennDraw.enableAnimation(frameRate) turns on animation at the specified framerate.
  • If animations are enabled, nothing will be actually drawn to the screen until PennDraw.advance() is called. When this function is called, any shape or text drawing commands run since the last call to advance() will have their outputs drawn to the screen.
• PennDraw also allows you to capture user input through mouse clicks and key presses. The protocols for these steps are listed here and you should take care to familiarize yourself with them.
  • Mouse presses are simple to read: calling mousePressed() works regardless of the previous user inputs and represents the state of the mouse at the current frame.
  • PennDraw tracks all key presses and saves them for you until you ask for them. Following the examples of how to use hasNextKeyTyped() and nextKeyTyped() are important for understanding how to read sequences of user input, which stores the state from previous frames.

Variables

What A Variable Is

Variables are just names for individual pieces of data in Java. You provide the name and type of a variable to Java, and Java will keep track of that name for you. You can then assign (and reassign) data to the variable for later use. Variables in Java are mutable, meaning that you are able to change the values that the variables contain. This is the big reason why they are so useful!

Declaring a Variable

The syntax for declaring a variable is a two part statement: type name, where type is the data type of the variable and name is the name of the variable. When a variable is declared without having a value assigned to it, the variable will have a default value. The default value depends on the data type that variable, but the result is that whenever you reference the variable after it is declared, it will have some (potentially null value). Once a variable has been declared, it is not possible to declare a variable of the same name in the same scope.
Some examples:

int x;
double y;
String lastName;
char middleInitial;
boolean isFinished;

Assigning a Value to a Variable

This is done with the use of the assignment operator, =. The syntax for assigning a value to a variable is: providing the name of the variable, followed by the assignment operator, followed by an expression that will be the new value of the variable (examples to follow). It is possible to assign a value to a variable at the moment it is declared, although this is not required. This means that it is possible to assign to a variable when or after it is declared, but it is not possible to assign a value to a name of a variable that has never been declared. Variables can also be assigned in terms of themselves, and this is a powerful asset in the case of trying to count or store intermediate results of computation.
Some examples:

int age = 53;
double y;
y = age * 2.5;
String lastName;
lastName = "Fouh";
middleInitial = (char) (middleInitial + 2);
boolean isFinished;
isFinished = !isFinished;

Variable Scopes

The scope of a variable is the set of lines in the Java program where Java will recognize the name of that variable. A variable is generally in scope for the entire code block in which it is defined following its definition, and it is also in scope for all code blocks nested inside after its definition.

public static void main(String[] args) {
  // x is not in scope
  System.out.println("not yet");
  boolean x = true; // x begins scope here
  while (x) {
    // this is a nested code block within the previous one
    x = false; // x is in scope here
    System.out.println("Just once.");
  }
  // we're back in the original block; x is in scope
  System.out.println(x);
} // x's original code block ends.
// x is not in scope here

public static int tester() {
  // x is not in scope here
}

Data Types

What a Data Type Is

In Java, every expression that stores or calculates to a value has a data type. A data type is a formal classification for how Java represents and handles any piece of information. This is a broad and almost philosophical definition. A more practical one looks like this: a data type in Java is a definition of the range that a particular value can belong to, and what operations are valid to perform on that value. Operators and functions in Java specify what data types they can work with. If you are not careful with tracking the data types of the inputs to different functions and operators, you can end up with code that won’t compile.

Primitive Data Types in Java

There are a number of primitive Data Types available in Java. To say that a data type is primitive means that the type is predefined by Java to be included in the language. In this class we focus on studying four primitive data types: boolean, char, int, and double. In addition, we are also heavily interested in the String Data Type which, while not technically a primitive one, can be used in many similar ways to the primitive data types.

Table of Primitives

Strings

Strings are effectively sequences of chars. The default value of a String is null (more on this later). Strings are how we represent text and language in Java. The operations defined on Strings are numerous, but an important basic one is the + operator, which represents concatenation when applied to one or more Strings.

Strings are immutable in Java, meaning that when you perform some operation on a String, an entirely new String will be returned.

String first = "Maya";
String second = first.toUpperCase(); // Capitalize all letters in string

System.out.println("first is still " + first);
System.out.println("second is " + second);

Running the above code demonstrates that String first was unchanged after the call to toUpperCase():

> first is still Maya
> second is MAYA

Some Important Operators & Tools

Many of the operators available for each data type will prove useful at some point. This section represents a brief overview of some of these, as well as other function tools. For a more complete overview of the behaviors of operations among different types, make sure to look at the exercises at the end of this presentation.

Relational Operators

All of >,<,<=,=>,==,!= are operators that accept two values of primitive data types and return a boolean result. These comparison tools are often essential for defining the control flow of your programs in if statements and in loops.

The multifaceted +

• When + is used between two numeric types (int and double), the resulting operation addition. If a double is in the mix, then the resulting type will be double; otherwise, int.
• When + is used between one String and any other primitive type, the result is concatenation. Concatenation converts the other data type in the operation to a String representation and then appends that to the other String.

  boolean b = false;
  String str = "hoods";
  System.out.println(b + str);
  // Output: "falsehoods"
  

• + can be used as addition between a char and another char or an int. This uses the underlying integer representation of the char to do the arithmetic. Using an int in this operation gives the output type int

Mod (%)

Another name for mod would be “remainder after division”. Major uses for this operation include constraining ints to wrap around within a certain range, testing for whether a number is even or odd, or checking to see if a number is a multiple of another. Remember that % with one negative argument leads to a negative result.

Casting

Casting is the process of interpreting a value of some data type as a different data type. In this course, when we refer to casting we are referring to the manual process of converting from a type with a wider range of values into a type with a smaller range of values.

int justTheInt = (int) 51.564;
char asLetter = (char) justTheInt;

Although we usually refer to it as “type promotion” in CIS 110, some sources will refer to conversions going in the other direction as casting, too. This is the automatic process of converting a char into an int or an int into a double that Java will do for you. This works automatically when the original type is “smaller” than the new, “larger” type.

Parsing

Parsing is the process of interpreting the value of a String as a representation of a value in some other data type. The primary ways that we use parsing with respect to data types are with the following two examples:

int fromString42 = Integer.parseInt("42");
double fromStringThreePointOneFour = Double.parseDouble("3.14159265");

Math

The basic arithmetic operators represent only a small fraction of the math that you can do in Java. Using the Math library, operations like abs, min, max, trigonometric functions, exponentiation, round, and random are available. There’s a good listing of these at the end of this presentation.

Conditionals

Conditionals are the simplest means we have to influence control flow in our programs. By default, Java programs execute sequentially, with each line being run in the order it’s written. When you add conditionals to your program, you decide among several options for which lines of code to be run next based on the state of some specified values.

When to use a Conditional

• To match some value to one out of several possible values
• To make a choice about what to do based on user input
• To make a decision about whether to break out of a loop
• To check to see if you’ve hit some special state, perhaps

if, else if, and else

Control flow can be influenced using if, else if, and else statements.

• An if statement consists of the if keyword, a condition, and a body. The condition is an expression, possibly containing several values and variables, that evaluates to a boolean.
  • If the condition evaluates to true, then the code in the body of the if statement is executed. - If not, then the code is skipped entirely.
• An else if statement is exactly like an if statement in syntax (it requires a condition and a body), with the only difference being that the required keyword is else if (rather than if alone).
  • An else if statement can only be used directly following an if statement or another else if statement.
  • When the condition of the else if statement evaluated to true and all previous if and else if statements were not executed, the body of the statement will be executed.
• An else statement is slightly different. Only the else keyword is required, along with a body.
  • An else statement can only be used once directly following an if statement or an else if statement
  • The body of an else statement will be executed only if all previous if and else if statements failed to execute.

if (x > y || a == c) {
  System.out.println("Hello");
} else if (x == y) {
  System.out.println("Goodbye");
} else if (x < y) {
  System.out.println("So long");
} else {
  System.out.println("Farewell");
}

// These next if statements are unrelated to the first chain and to each other.
// Either of them will be run when their conditions are true, independent of prior conditionals.
if (u && i) {
  return 10;
}
if (me && u) {
  return 20;
}

Switch Statements

Switch statements are conditionals designed for the purpose of checking the value of some variable or expression against several enumerated outcomes. We do not require you to use a switch statement in this class, although you are certainly welcome to. An example that demonstrates the complete syntax of a switch statement is presented here.

switch (name) {
  case "Harry": case "Eric":
    title = "Professor";
    break;
  case "Jules": case "Michael": case "Gian": case "Ben":
    title = "Head TA";
    break;
  default:
    System.out.println("Name not matched, default case used");
    title = "TA";
    break;
}

This example checks to see if name is the name of a professor, a head TA, or a TA.

Loops

Loops are the way that we implement iteration in Java. They are the tools by which we are able to write programs that perform one task many, many times. It is from this ability to write in repetition (with controlled variation) that the power of computation emerges.

Rules of Iteration in Java

Any loop that we use in Java is controlled by three components:

1. An initialization of a loop control variable (or perhaps several variables).
2. A termination condition defined over the control variable(s). When the loop control variable reaches a particular value or state, the termination condition will evaluate to false and the iteration of the loop will stop.
3. A modification of the loop control variable(s). By modifying the control variable(s), we can eventually reach the state outlined in the termination condition, indicating that the loop should cease repeating.

The While Loop

As outlined in the previous section, a while loop must include an initialization component, a termination condition, and a modification step.

int i = 40; // initialization (i is the loop control variable)
while (i > 0) { // termination condition
  System.out.println(i);
  i--; // modification step
}

boolean hasPressed = false; // initialization (hasPressed is the loop control variable)
while (!hasPressed) { // termination condition
  PennDraw.filledRectangle(...);
  if (PennDraw.mousePressed()) {
    hasPressed = true; // modification
  }
}

Some takeaways from these two examples:

• You will usually need to perform the initialization step outside of the body of the loop. Otherwise, loop control variable will have its value reset every iteration of the loop, leading to bugs.
• The termination condition is the only essential component of iteration that’s actually required by the syntax of the while loop.
• The loop control variable need not be modified every iteration of the while loop, although sometimes it makes sense to. Compare how many times hasPressed would be changed with how many times i would be changed.

The termination condition is checked before every iteration of the loop, including before the (potential) first iteration.

The For Loop

A for loop must again include an initialization step, a termination condition, and a modification. Unlike a while loop, though, a for loop has space for these steps built into its very syntax.

//  |INITIALIZATION   | TERMINATION COND. | MODIFICATION|
for (String line = "."; line.length() < 10; line += '.') {
  System.out.println(line);
}

//  |INIT.         | TERM. |  MODIF.|
for (double k = 100; k == 1; k /= 10) {
  System.out.println(k);
}

//  |INIT.    | TERM.          | MOD|
for (int i = 0; i < args.length; i++) {
  System.out.println(args[i]);
}

A variable initialized during the intialization step is in scope only in the body of the loop. The termination condition is checked before every iteration of the loop, including before the (potential) first iteration. The modification step is performed after each iteration.

Your Loop of Choice

It is possible to convert a loop of one variety into an equivalent loop of the other variety. This is always true, although it usually is somewhat more natural to use one type in certain circumstances.

It’s often more natural to write a while loop when:

• You’re doing animation
• You’re waiting indefinitely for user input
• The purpose of your iteration is not to traverse over some data of fixed length, or you’re traversing over some data that has an unknown length
• You will perform different modification steps over the course of the loop execution based on different states

It’s often more natural to write a for loop when:

• You’re looping over the indices of data of some fixed length
• You need to generate a range of numbers
• You have a specific number of times that you want your loop to execute.

Perhaps the most salient point here: if your problem can be phrased as “examine every x in y” or “for every element of this array/this string, do something”, this is a good sign that a for loop would fit nicely. These are just general guidelines, and you should keep in mind that you can always make either loop work.

Break and Continue

break is a statement that, when executed in the body of a loop, causes that loop to immediately stop executing. The current iteration is halted, and no further iterations are executed. The control of the program resumes immediately after the body of the loop.

continue is a statement that, when executed in the body of a loop, causes that iteration of the loop to immediately cease. In the case of the for loop, this causes the modification step to be applied. As long as the termination condition has not been met, the next iteration of the loop will commence.

break exits a loop entirely, continue skips to the next iteration.

Arrays

What is an Array?

In Java, an array is an fixed-length, indexed sequence of values that are all of the same type. Each value in this sequence can be modified and overwritten. An array is a data type of its own, and the type of an array is different from the type of the elements it contains. In particular, int x = 4; defines a variable of type int, whereas int[] xs = {3, 4, 5}; defines a variable of type int[] (note the difference in brackets).

int[] ages = new int[320]; // an array of 320 ints
ages = new int[60]; // a new array of 60 ints. It is valid to store a new array in ages.

double[] xPositions = new double[10];

String[] suits = {"spades", "hearts", "diamonds", "clubs"};

Arrays Are Fixed-Length

When you create an array, you must also specify its length. This can be done with implicit initialization (e.g. new char[4]) or explicit (e.g. {4, 3, 2, 1}). In both of these example cases, the arrays have a length of 4. It is not possible to add another element to this array without first creating a new, larger array.

Arrays Are Indexed

Arrays in Java are 0-indexed, meaning that we refer to the first element of an array as being at index 0. Using .length on the end of the array, we have an expression for the length of an array. If we have some array arr, and we say that n is equal to arr.length, then each integer between 0 and n (but not including n) is a valid index for that array.

The syntax for indexing into arrays in Java is to append [index] to the end of a variable containing an array. Taking our example from above with suits:

String[] suits = {"spades", "hearts", "diamonds", "clubs"};

Then the following table represents the indices of suits:

Arrays Contain Values Of One Type Only

When an array is initialized without explicit values, we use the syntax new type[length], where type represents some valid data type (String, boolean, etc). The array that is created thus has the data type type[], which reads in English as “an array of types” or a “type array”. This new array can only contain values of data type type from now on.
This also means that when initializing arrays with explicit values, those explicit values must all be of the same type.
When declaring a variable that will contain an array, you must declare the variable of the correct type. Refer the previous examples under “What is an Array?”.

Manipulating Arrays

Presented here are a few examples of how to manipulate arrays. These are taken directly from the website of the course’s textbook. All credit to Sedgewick and Wayne. Refer to the booksite’s section on arrays for a fuller listing of patterns related to using arrays.

Initializing entries of an array to random values

int n = 5;
double[] a = new double[n];
for (int i = 0; i < n; i++) {
    a[i] = Math.random();
}

Printing the values of an array

Assumes the existence of some array a, like the one from the first example.

System.out.println("a[]");
System.out.println("-------------------");
for (int i = 0; i < n; i++) {
    System.out.println(a[i]);
}
System.out.println();
System.out.println("a = " + a);
System.out.println();

Finding the maximum value in an array

Assumes the existence of some array a, like the one from the first example.

double max = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n; i++) {
    if (a[i] > max) max = a[i];
}
System.out.println("max = " + max);

Finding the sum & mean of an array of doubles

Assumes the existence of some array a, like the one from the first example.

double sum = 0.0;
for (int i = 0; i < n; i++) {
    sum += a[i];
}
System.out.println("average = " + sum / n);

Functions

Functions (or methods) are the basic building blocks of Java programs. main is a function, Math.abs is a function, PennDraw.filledRectangle is a function, and you can write your own functions. In CIS 110, we use the terms “function” and “method” to refer to the same thing. Both the term “function” and the term “method” have broader and diverging meanings outside of the scope of the course, but in CIS 110 we can use them interchangably.

In JavaScript, it’s not the case that every function is a method although the reverse is basically true. Going by the definitions outlined in, say, Cornell’s CS1130 Course, Java has it so that not every method is a function even though every function is indeed a method. This is vague notation.

Functions in Java are similar to functions in mathematics. Fundamentally, functions are tools that take some inputs, do some work based on the inputs, and produce some output.

Anatomy of a Function

A function has…

1. a header. A header consists of several pieces:
   1. One or more optional modifiers, like public and static. You should continue to include these words at the beginning of your functions, even though we haven’t covered their meanings yet.
   2. A return type. This specifies the data type that the function is guaranteed to output.
      1. If a function has a return type of int, for example, the function is guaranteed to return an int.
      2. It is possible for a function to have a return type of void, which is a guarantee that the function will not return any data at all.
   3. A name. This specifies how you can refer to this function and use it later.
   4. A list of arguments type & name pairs
      1. Each argument must have its type specified first
      2. The name of the argument in the header puts variables with these names in scope in the body of the function.
2. a body. The body of a function is a just another block of code where execution starts at the top.
3. one or more return statements.
   1. return is a keyword in Java that indicates that the function should stop executing.
   2. return is coupled with a value. For example, a full return statement might look like return true;, return x + 4;, or return str.toUpperCase(). In each case, the type of the value being returned must match the return type of the function.
   3. A function with a non-void return type must end with a return. Reaching the end of a function without hitting return will result in an error.
   4. The only exception to these rules are in the case of a function with return type void. In this case, return cannot be paired with a value, since void indicates that no data is returned. In functions with return type void, it is possible to use no return statements at all, and when Java reaches the end of the function body, Java will return implicitly.

To illustrate these rules, we examine a searching function:

/**
 * indexOfValue attempts to find value in an array of chars
 * called list. If we find value, return its index. If we
 * don't find value, return -1 to indicate that value is 
 * not in list.
 */
public static int indexOfValue(char value, char[] list) {
  for (int i = 0; i < list.length; i++) {
    if (list[i] == value) {
      return i;
    }
  }
  return -1
}

• The header is public static int indexOfValue(char value, char[] list)
  • The return type of this function is int
  • The name of the function is indexOfValue
  • The input argument consists of a char named value and an array of chars (a char[]) named list.
• The body of the function lives between the first open brace and the last close brace. list and value, the input arguments, are in scope in the body.
• This function has two return statements, and both of them return some int value. No matter the inputs, one of these returns will be reached.

Functions and Control Flow

Java programs start executing at main when run from the command line, as we do in CIS 110. Control is passed between functions with function calls, which happen where we write the name of the function followed by a list of input argument values in parentheses.

Considering the example below, we have a function public static int addTwo(int x). We can call addTwo like so: addTwo(4). In this case, 4 is the value that will be bound to the variable x at the start of addTwo’s body.

The execution of the most recent function call must be completed before control is passed back to the point where that call was made. This results in a call stack.

public class Functions {
    public static void main(String[] args) {
        System.out.println("Starting main.");
        int six = addTwo(4);
        System.out.println("four plus two is " + six);
        int eight = addThree(5);
        System.out.println("five plus three is " + eight);
        System.out.println("Leaving main");
    }

    public static int addTwo(int x) {
        System.out.println("Starting addTwo with input " + x);
        System.out.println("Leaving addTwo");
        return x + 2;
    }

    public static int addThree(int x) {
        System.out.println("Starting addThree with input " + x);
        int temp = addTwo(x);
        System.out.println("Leaving addThree");
        return temp + 1;
    }
}

The output:

$ java Functions
Starting main.
Starting addTwo with input 4
Leaving addTwo
four plus two is 6
Starting addThree with input 5
Starting addTwo with input 5
Leaving addTwo
Leaving addThree
five plus three is 8
Leaving main

Observe how this output illustrates the call stack. main is called first. From main, we call addTwo, which returns 6 without calling another function. Then from main, we call addThree, which in turn calls addTwo. addThree’s call to addTwo is resolved before addThree returns the result back to main. Then, main finishes execution without a return statement, which is acceptable because main always has return type void.

Functions and Variable Scope

When a function is called and its body is executed, Java creates a new scope. Generally speaking, the only variables that will be in scope at the start of the function execution will be the input arguments to that function.

public class Scope {
  public static void main(String[] args) {
        int a = 50;
        int b = 100;
        int c = 200;
        System.out.println("before newScope, main's c = " + c);
        newScope(a, b);
        // the variable c declared in newScope is out of scope
        // back here in main.
        System.out.println("after newScope, main's c = " + c);
    }

    public static void newScope(int x, int y) {
        System.out.println("STARTING newScope");
        // x and y are in scope
        System.out.println("x = " + x);
        System.out.println("y = " + y);

        // a, b, and c are not in scope here.
        // we can declare a variable c here
        int c = 40;
        System.out.println("newScope's c = " + c);
        System.out.println("ENDING newScope");
    }
}

Output:

$ java Scope
before newScope, main's c = 200
STARTING newScope
x = 50
y = 100
newScope's c = 40
ENDING newScope
after newScope, main's c = 200

Recursion

Recursion is a strategy of programming that uses a solution that’s determined in terms of itself. The recursive answer to the question of how long a given String is might be “one character longer than the length of this String without its first character.” This might seem like an unhelpful answer, but if we combine it with the knowledge that an empty String has a length of 0, then we’re actually approaching a solution. How long is "Java"? Well, it’s one character longer than "ava", which itself is one character longer than "va", which itself is one character longer than "a", which itself is one character longer than "", which has a length of 0 characters. All together, that means that "Java" is 1 + 1 + 1 + 1 + 0, or 4 characters long.

Here’s a look at the above algorithm written in Java.

public static int myLength(String s) {
  if (s.equals("")) { //base case
    return 0;
  }
  return 1 + myLength(s.substring(1)); //recursive case
}

Essential Components of a Recursive Algorithm

• First, and most important, is the base case. This is the input (or class of inputs) for which the solution is immmediately calculable. Your recursive function may need more than one base case!
  • In the string length example, the base case was the input "": the empty string. In this case, the output of the algorithm should always be 0.
  • In the case of a searching algorithm, we might have two base cases: one for when there are no elements left to search, and another for when the element in the array we’re searching through is the element we’re looking for. In both of these cases, there’s no need to make further recursive calls since we’ve no need to keep searching!
• Second is the recursive case. This is the case when we need to make a recursive call to the function we’re using to solve the problem. Two important factors to consider when designing a recursive call: how will I change the input so that it gets “closer” to a base case? and how will I combine the output of the recursive call with another value so that the final solution is correct?
  • In the case of myLength, our recursive call is myLength(s.substring(1)). This means that the inputs in each of the successive recursive calls will always be shorter, and therefore closer to matching the empty string of the base case.
  • The value that’s returned in the recursive case is 1 + myLength(s.substring(1)). Notice that this combines the result of the next recursive call with a partial solution (1, which is the number of characters that we “peeled” off the front of s before making the recursive call).

Tracing Recursion

Any time a recursive call is made, that call must be fully evaluated before the rest of the function can evaluate. This holds true for the successive recursive calls too, leading to multiple calls awaiting execution on a “call stack” that Java manages for us.

You can explore the execution of a recursive fibonacci function here.

Unit Testing

Unit testing is an essential practice for efficient and correct programming. It is useful for helping to define expected behaviors and it allows a programmer to check for correctness in the work that they’ve done.

In order to write unit tests in Java, we make use of JUnit.

Essentials of a Test Case

A test case is a way of testing the behavior of a small unit of code, typically a function, when run with a particular input (or set of inputs). Thus, the essential components for defining any test at a high level are:

1. Inputs. These are the pieces of data that you’d like to see how your code handles. If you’re unit testing a search function, your input would be some particular array of Strings and a target String.
2. Expected Output. This defines the value that your unit of code should evaluate to or return after being run on your chosen inputs. If your inputs to search were String[] arr = {"Harry", "Jules", "Michael"} and String target = "Jules", then the expected output of search(arr, target) would be 1, which is the index at which "Jules" can be found in the input array. You determine the expected output for a test by manually examining the inputs and the desired behavior of the function; you do not actually run the unit of code to generate this value!
3. Actual Output. This is the actual value that your unit of code returned after being run on your chosen inputs. The actual output is evaluated by running the unit of code you’re testing on the inputs that you chose. That is, int actual = search(array, target) in this case.
4. Assertion Statement. The assertion statement is the part of the JUnit test case that checks to see if the expected output matches the actual output. There are actually very many assertion statements one can use, but we mostly focus on assertEquals. That is, the assertion statement for the searching example might then look like assertEquals(expected, actual). In fact, you should usually provide a String as well that explains the purpose of the test case. That is: assertEquals("searching for Jules in array {Harry, Jules, Michael}", expected, actual).

Anatomy of a JUnit Test File

import static org.junit.Assert.*;
import org.junit.*;

public class SearchingTest {
    @Test
    public void TestSearchJulesInArrayWithJulesOutputs1() {
        String target = "Jules";
        String[] array = {"Harry", "Jules", "Michael"};
        int expected = 1;
        int actual = Searching.search(array, target);
        assertEquals("searching for Jules in array {Harry, Jules, Michael}", expected, actual);
    }
}

Of note:

• The name of the test class is SearchingTest. Having this class name end with Test tells us we’re testing something here, specifically functions from a class called Searching.
• Our test case is actually a function.
  • Before the function is @Test. Don’t forget to include this above each test case! It tells JUnit that what follows is indeed a test case.
  • The test case has a terrible long name. This is a feature of testing: make sure to name the function something that includes info about what’s being tested, the inputs, and the expected outputs.
  • The return type of the function is void.
  • The function declaration has public but not static. This is intentional; keep it that way.
• The body of the function sets up variables to store the input(s), the expected output, and the actual output. Note that expected is assigned a value that does not include a call to search, whereas actual is assigned exactly the value of calling search on our chosen inputs.
• The assertEquals statement concludes the test and compares our expected and actual outputs. If the test fails, JUnit will show us a the String that we provided as an explanation to help remind us what we were intending to test.

Passing and Failing Tests

If a test is shown to pass, that means the expected output matched the actual output. Note that this doesn’t necessarily mean that your code is absolutely correct! You could have written the test incorrectly, or you could have chosen an input that works while most other inputs would cause the test to fail.

If a test is shown to fail, that means the expected output did not match the actual output. This might mean that there’s a bug in the unit of code you’re testing, or it might mean that you made a mistake when writing your test.

Testing helps you sniff out when your code isn’t working properly, but without a careful eye and a broad set of tests, it’s possible to miss what you’re looking for. Test carefully, and test widely.