Data flow Flashcards
What is a parameter?
All the methods we’ve written so far did exactly the same thing every time we called them. Some methods can be more useful if we can give them a value that they can use to help determine their output. For example, here’s a method that computes 2 raised to the 6th power:
public static void power2exp6() {
System.out.println(“2 to the 6 = 64”);
}
Not very useful. But, if we could tell the method what exponent to use, it would be much more useful. Java lets us do this by declaring a parameter of a specific data type for the function inside the parentheses. This parameter essentially declares a variable inside the method. In the method below, the parameter is int exp so we can reference the variable exp in the method. Of course, the method now needs to actually compute the value, so we do that with a for loop that does repeated multiplications:
public static void power2(int exp) {
result = 1;
for (int i = 1; i <= exp; i++) {
result *= 2;
}
System.out.println(“2 to the “ + exp + “ = “ + result);
}
To call this method, we need to “pass it” a value to use for exp, which we do inside the parentheses of the call:
power2(6);
When the method executes, it assigns the value passed into it (6) to the variable declared by the formal parameter (exp), so it would output the same result as before:
2 to the 6 = 64
So, we could also call it with any other integer we wanted to and it would compute and output the corresponding result:
power2(16); // 2 to the 16 = 65536
power2(0); // 2 to the 0 = 1
power2(7); // 2 to the 7 = 128
We could make this even more useful if we could use it to compute the power of any number, not just 2. To do this, we can simply add a second parameter with a different name:
public static void power(int base, int exp) {
result = 1;
for (int i = 1; i <= exp; i++) {
result *= base;
}
System.out.println(“base to the “ + exp + “ = “ + result);
}
To get the same result as before, the call would be:
power(2,6);
The order of the parameters is very important: it determines which value is used as the base and which for the exponent. If we declared the method instead as:
public static void power(int exp, int base)
The same call would then have output 62 instead of 26 because the first parameter (2) would have been used to set the value of variable exp, and the second (6) would have set base.
Can we pass variables to a method rather than literals?
It’s very common to pass variables to a method rather than literals; for example, to print all the powers of 2 up to 16:
for (int i = 0; i <= 16; i++) {
power(2,i);
}
Note that the value of i in the call is used to set the value of the variable exp in the method; there is absolutely NO requirement that these two variables use the same name because it’s the order of the parameters that determines which is assigned to which. Even if you used the same name like this:
for (int base = 0; base <= 16; base++) {
power(2,base);
}
… the two variables named base are NOT the same: one is in the scope of the method, and the other is in the scope of the calling program; this is a good thing, because two different people can write the method and calling program, and each can use any variable names that make sense in their specific code. This means you CANNOT change the value of a parameter passed into a method in the method. We’ll see later how to return a value from a method and use it to change the value of a variable in the calling program if that’s what you really want to do.
You also CANNOT pass our power method a double value or variable for either the base or the exponent. Java will give you an error message just as it would if you tried to assign a double value to an integer variable. If we wanted to support this, we could simply change our method signature (the list of formal parameters) to:
power(double base, int exp);
… since our for loop works just as well with a double as the base. Because you can assign an int to a double, we could then call it with either:
power(2,6);
power(2.3,6);
What is method overloading?
Our power method from the last section as written would _not_ work correctly with a double as the exponent.
public static void power(int base, int exp) {
result = 1;
for (int i = 1; i <= exp; i++) {
result *= base;
}
System.out.println(“base to the “ + exp + “ = “ + result);
}
If we did want to write a fancier version of power to handle real number exponents, Java lets us call it by the same name, but with a different method signature:
public static void power(double base, double exp) {
// Kasey write better code here
}
Java calls this ability to have different methods of the same name but with different signatures method overloading. The data types of overloaded methods must be different, or in different orders so that Java knows which code to execute for a specific method call.
Method overloading lets the writer of the method do a little more work to make things easier for the programmer who wants to use the method. That’s why println() is overloaded to let you give it an int, double, String, or boolean without having to call printlnInt, printlnDouble, etc. It’s also a good way to provide for a common default value that the caller doesn’t have to provide. We could default our power function to use a base of 2 by defining this overloading of the method that simply calls our 2-parameter version:
public static void power(int exp) {
power(2, exp);
}
What is a return statement?
Parameters allow us to pass information to a method for it to use. In many cases, we’d like to get some information back from a method that we can use in the calling program. The power function we wrote in the last section wrote the result of its computation to the console in a message, but what if we wanted to use that value to, say, find the base and exponent closest to a specific integer? Our program has no way of getting the result into a variable to use it. What if we just passed another parameter for the method to put the result in?
public static void power (int base, int exp, int result) {
Some programming languages work this way, but remember that Java creates new variable for every parameter in the method, and copies the values passed in. It does NOT copy values back the other way! So, if we call this revised method like this:
int x = 0;
power(2,6,x);
System.out.println(x);
… it would print 0, not 64 because power() can’t change the value of the parameter x.
Java does provide a way to do this with the return statement. Here’s our power method modified to return the result rather than print it to the console:
public static int power(int base, int exp) {
result = 1;
for (int i = 1; i <= exp; i++) {
result *= base;
}
return result;
}
We changed the return type in the method header from void to int so that we can return an integer value, and as the last statement of the method we used the return statement to return the value we computed.
What is the syntax for using returns?
To allow a method to return a value you must tell the computer what type of value you are going to return in the method header, and in the body of the method you must at some point include the “return” keyword:
public static ReturnType myMethod(parameters) {
return ReturnTypeData;
}
Note that when Java encounters a “return” it immediately ends the method and returns to the line on which that method was called. Therefore, any line after a return is considered “unreachable”.
The value we return becomes the value of the method call expression, so we can simply assign it to a variable in the calling program:
int x = power(2,6);
We can also use it directly in an expression:
System.out.println(power(2,6));
We’ve actually done this before when we used the boolean return value of the equals() method with Strings:
if (name.equals(“John Doe”)) {
What are some rules to follow when returning a value from a method?
- A method can return one value of a specific data type. You must specifiy that data type in the method header.
- The method must return a value of that data type as the last thing it does. It won’t execute any code after the return statement.
- The calling program must immediately use the value of the method call: store it in a variable, use it in an expression, pass it as a parameter to another method. If it doesn’t, the value is essentially lost.
What are some features to of Java Math class?
The Java Math class has lots of common math functions implemented as methods. They take parameters and provide return values as shown below. We’ve separated them into “essential” and “useful” ones to help you focus on which ones will come up most often, but there are even more in the Java documentation! Some of these use method overloading to let you pass parameters and get return values of any numeric type including int and double; these are shown as < any > below. Remember, you can pass an int (or float) anywhere a double is required and Java will automatically convert it for you.
What is the index of a String?
Now that we understand more about methods, parameters, and returns, we can dive more deeply into the String class and its methods. We’ve already used methods that deal with the String as a whole (like equals and contains); now it’s time to look inside a String object.
As you already know, a String is actually a collection of individual characters or “chars”. The individual characters of a string are numbered from 0 to length()-1; this number is called the index of the character in the String.
What does the length() method do in a String?
The length() method returns the number of characters a string contains:
“John Doe”.length() // returns the integer value 8
”“.length() // returns 0
We’ll use String literals in many of our String method examples for simplicity, although typically you’ll apply these methods to variables. For example, if we assigned the value “John Doe” to the string variable name, then we get the same results as above:
String name = “John Doe”;
name.length() // returns 8
Note: because the index of the first letter is 0, the index of the last letter is length()-1
What is a substring method()?
We can extract any part of a String using the substring() method. substring() takes integer parameters specifying the index of the first character of the substring to return, and optionally the first character NOT to return. You can think of the first parameter as “inclusive” and the second as “exclusive” of the String returned. Thanks to method overloading, if you just specify the first index, substring() will default the second argument to length() and so return all the rest of the String.
Note that substring() will end your program with an error if you specify an index outside the range of 0 to length(), or if the beginning index is greater than the ending index.
What is an indexOf() method?
The indexOf() method returns the index of the first occurrence of a substring in a String. If the substring is not found in the String, it returns -1. Thanks to method overloading, you can pass it a String or char.
What are some other useful String methods?
Here’s a summary of some other commonly used String methods. You can find all the different ones in the official Java documentation. You can of course pass in a char for any String parameter and Java will convert it for you.
What is recursion?
Any Java method has a very interesting ability: it can call itself! This capability is called recursion, and it is an extremely powerful way to solve some kinds of computing problems.In fact, it’s the most natural way to do things like searching your computer for a specific file, or finding the best way to get from one place to another on a road map
What is the syntax for using a recursion method?
Let’s look at an example: computing the factorial of a number. A factorial is a mathematical sum of all preceding ints. For example 5! = 54321.
Here is how we would use a loop to calculate this:
public static int factorial(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
We can also code this using recursion. The secret to thinking recursively is “how can I break this down to simpler and simpler problems?”
In this case if you need to find 5!, you could first find 4! and then just multiply that by 5, but let’s not stop there. To find 4! you could find 3! and just multiply that by 4. And so on until you get to the very simplest problem- 1! = 1.
factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1
Looking at the pattern, we could generalize it as:
factorial(n) = n * factorial(n-1)
Now let’s turn this into code:
public static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n-1);
}
}
The first return, inside the if statement is called the “base case”: it’s the smallest possible version of the computation, the one that’s “easy”, or the “end of the recursion”.
Inside the else is the recursive case where we’ve made the problem smaller before passing it onto the next method call recursively.
As this suggests, a recursive method always needs:
- A base case that returns a value without calling itself. This is how you know your recursion will actually stop.
- A recursive case that makes the problem smaller, and then calls itself recursively to solve the smaller problem. You have to make sure your recursive case moves your parameter closer to the base case, otherwise you might recurse for forever.
Can a recursive method have multiple base cases and multiple recursive calls?
In some cases, you may have several base cases, and the recursive case may make multiple recursive calls and/or different calls depending on the values passed in.
The Fibonacci sequence is an example of a naturally occurring recursive algorithm. It involves multiple base cases and multiple recursive calls. In this sequence, each number is the sum of the previous two, starting with 1 and 1:
Fibonacci(1) = 1 = base case
Fibonacci(2) = 1 = base case
Fibonacci(3) = 2 = 1 + 1
Fibonacci(4) = 3 = 1 + 2
Fibonacci(5) = 5 = 3 + 2
Fibonacci(6) = 8 = 5 + 3
You can see this as a pattern:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
Which represents the recursive case, because it breaks the problem down into smaller and smaller versions of itself.
To code this we need two base cases, since we have to know first two numbers in the sequence to get it started:
fibonacci(1) = 1 fibonacci(2) = 1
If we combine the recursive case and the base case we get the following solution:
public static int fibonacci(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 1;
} else { return fibonacci(n-1) + fibonacci(n-2);
}
}
In all recursive methods, if the base case is missing, or if the recursive case can ever call itself with the same problem (same values of the parameters), it can call itself forever. In Java, this results in a “stack overflow” error eventually when it runs out of memory on the computer.
What is “recursive tracing”?
It takes practice for most people to get comfortable “thinking recursively”. Tracing recursive algorithms as they work is a good way of getting comfortable with how this method works. We could do this by writing out the formulas, one after another, like we did for factorial in the previous section:
factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1
However, this can get very long winded. To make recursive tracing simpler we can do the same thing in an abbreviated table that shows the value passed to each recursive call in order:
Besides a linear table, how else can one visualize a recursive solution?
When you have a recursive solution with multiple recursive calls each one kicks off it’s own table, which can be hard to keep track of. This is because for each call you have two more recursive calls to make, and each of those have two more recursive calls and so on… Instead of a linear table you can visualize this like a tree that branches out as it moves down towards the base case.
Let’s take Fibonacci from the last section:
public static int fibonacci(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
Here is a “tree” of recursion for fibonacci(5):
