Learning Java: �A Test-Driven Approach
Chapter 2.3: Loops
What is a loop?
Loops are ways to repeat something, as its name suggests.
Recall tail recursion; we said that we can mechanically convert ANY tail recursive method into one that uses an equivalent loop.
Because we are all familiar with recursion (but not everyone is familiar with a loop), we’ll follow a translation pipeline.
Translating factTR into a loop.
Let’s translate the tail recursive version of factorial into a loop.
Recall its implementation.
private static int factHelper(int n,
int acc) {
if (n == 0) {� return acc;� } else {� return factHelper(n - 1, n * acc);� }
}
static int factTR(int n) {
return factHelper(n, 1);
}
Step 1: color-coding the recursion.
We identify:
Color-code them differently!
private static int factHelper(int n,
int acc) {
if (n == 0) {� return acc;� } else {� return factHelper(n - 1, n * acc);� }
}
static int factTR(int n) {
return factHelper(n, 1);
}
Step 2: initializing the local variables.
Move all “accumulator” variables into the body of the function as local variables.
The local variables should be initialized to their starting values from the driver.
Index variables, e.g., i, are treated like accumulators
static int factTR(int n) {
return factHelper(n, 1);
}
private static int factHelper(int n,
int acc) {
if (n == 0) {� return acc;� } else {� return factHelper(n - 1, n * acc);� }
}
static int factLoop(int n) {
int acc = 1;
…
}
Step 3: designing the condition.
Write the “while” keyword below the local variables.
Negate the base case using “!”.
static int factLoop(int n) {
int acc = 1;
…
}
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
}
…
}
Step 4: designing the body.
A while loop body is a sequence of statements.
These statements, in general, modify the accumulators/variables.
Take the updated variables and morph them into assignment updates:
parameterName = expr
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
}
…
}
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
acc = acc * n;
n = n - 1;
}
…
}
Step 4: designing the body.
Careful! The order of update statements is significant!
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
n = n - 1;
acc = acc * n;
}
…
}
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
acc = acc * n;
n = n - 1;
}
…
}
fact(5) = 120
fact(5) = 24
Step 5: returning the value(s).
Take the atomic value and return it from the function after the loop body.
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
acc = acc * n;
n = n - 1;
}
…
}
static int factLoop(int n) {
int acc = 1;
while (!(n == 0)) {
acc = acc * n;
n = n - 1;
}
return acc;
}
Translating fibTR into a loop.
Let’s translate the tail recursive version of fibonacci into a loop.
Recall its implementation.
private static int fibHelper(int n,
int a,
int b) {
if (n == 0) {� return a;� } else if (n == 1) {
return b;
} else {� return fibHelper(n - 1, b, a + b);� }
}
static int fibTR(int n) {
return fibHelper(n, 0, 1);
}
Step 1: color-coding the recursion.
private static int fibHelper(int n,
int a,
int b) {
if (n == 0) {� return a;� } else if (n == 1) {
return b;
} else {� return fibHelper(n - 1, b, a + b);� }
}
static int fibTR(int n) {
return fibHelper(n, 0, 1);
}
Step 2: initializing the local variables.
static int fibTR(int n) {
return fibHelper(n, 0, 1);
}
private static int fibHelper(int n, int a, int b) {
if (n == 0) {� return a;� } else if (n == 1) {
return b;
} else {� return fibHelper(n - 1, b, a + b);� }
}
static int fibLoop(int n) {
int a = 0;
int b = 1;
…
}
Step 3: designing the condition.
static int fibLoop(int n) {
int a = 0;
int b = 1;
…
}
static int fibLoop(int n) {
int a = 0;
int b = 1;
while (!(n == 0 || n == 1)) {
}
}
If you have multiple base cases, combine them with ||.
Step 4: designing the body.
static int fibLoop(int n) {
int a = 0;
int b = 1;
while (!(n == 0 || n == 1)) {
}
}
static int fibLoop(int n) {
int a = 0;
int b = 1;
while (!(n == 0 || n == 1)) {
int tempA = a;
a = b;
b = tempA = b;
n = n - 1;
}
}
We have a problem! a uses b and b uses a in the recursive call.
Solution: use a temporary variable.
Step 5: returning the value(s)
static int fibLoop(int n) {
int a = 0;
int b = 1;
while (!(n == 0 || n == 1)) {
int tempA = a;
a = b;
b = tempA = b;
n = n - 1;
}
}
static int fibLoop(int n) {
int a = 0;
int b = 1;
while (!(n == 0 || n == 1)) {
int tempA = a;
a = b;
b = tempA = b;
n = n - 1;
}
if (n == 0) {
return a;
} else {
return b;
}
}
Remember that there are two ways to get to the base case: either n = 0 or n = 1.
Why use a translation pipeline?
IT ALWAYS WORKS!
There are so many ways that programmers mess up loops.
The translation pipeline guarantees that, if the tail recursive method is correct, the loop method will be correct.
Let’s work with an example of going from standard recursion to tail recursion to loops.
Translation pipeline example.
Example: Design the String replaceUpperWithLower(String s) method that replaces all occurrences of uppercase characters with their lowercase counterpart.
import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;
class ReplaceUpperWithLower {�
@Test
void testReplaceUpperWithLower() {
assertAll(
() -> assertEquals(“hello world!”, replaceUpperWithLower(“hELLo WoRlD!”)),
() -> assertEquals(“hello”, replaceUpperWithLower(“hello”)),
() -> assertEquals(“hi”, replaceUpperWithLower(“HI”)),
() -> assertEquals(“”, replaceUpperWithLower(“”)));
}�}
Translation pipeline example.
Remember: recursing over strings is inefficient - add an index and a helper method!
class ReplaceUpperWithLower {
static String replaceUpperWithLower(String s) {
return rUWLHelper(s, 0);
}
}
private static String rUWLHelper(String s, int i) {
if (i == s.length()) {
return “”;
} else if (Character.isUpperCase(s.charAt(i))) {
return Character.toLowerCase(s.charAt(i)) +
rUWLHelper(s, i + 1);
} else {
return s.charAt(i) + rUWLHelper(s, i + 1);
}
}
Translation pipeline example.
Tail recursive method:
class ReplaceUpperWithLower {
static String replaceUpperWithLowerTR(String s) {
return rUWLTRHelper(s, 0, “”);
}
}
private static String rUWLTRHelper(String s,
String acc,
int i) {
if (i == s.length()) {
return acc;
} else if (Character.isUpperCase(s.charAt(i))) {
return rUWLTRHelper(
s, acc+Character.toLowerCase(s.charAt(i)),i+1);
} else {
return rUWLTRHelper(s, acc+s.charAt(i),i+1);
}
}
Both i and acc are accumulators!
‘+’ over strings is not commutative! The recursive call “moves” left.
Translation pipeline example.
Loop:
static String rUWLLoop(String s) {
int i = 0;
string acc = “”;
while (!(i == s.length())) {
if (Character.isUpperCase(s.charAt(i))) {
acc = acc + Character.toLowerCase(s.charAt(i));
i = i + 1;
} else {
acc = acc + s.charAt(i);
i = i + 1;
}
}
return acc;
}
The while loop.
A while loop is define as, “while p is true, do body.”
while (p) {
// body.
}
Therefore, !p is true when the loop finishes.
We can use that reasoning to easily figure out what is true when a loop terminates.
The while loop condition.
Example #1: What is true when this loop finishes:
while ((x == 5) && !(y < 10))?
= !((x == 5) && !(y < 10))
= (!(x == 5) || !!(y < 10)) // DeMorgan’s law
= (x != 5 || y < 10) // Eqv.
The while loop condition.
Example #2: What is true when this loop finishes:
while (!((p == x + 10) && (q == false || r == true)))?
= !!((p == x + 10) && (q == false || r == true)))
= ((p == x + 10) && (q == false || r == true)))
Do you see why the translation pipeline makes it easy to identify terminating loop conditions?
Another translation example.
Sometimes a method is naturally represented using tail recursion.
Example: Euclid’s algorithm:
gcd(x, y) = if y == 0 then x
if y > x then gcd(y, x)
else gcd(y, x % y);
Another translation example.
static int gcdTR(int x, int y) {
return gcdHelper(x, y);
}
private static int gcdHelper(int x, int y) {
if (y == 0) {
return x;
} else if (y > x) {
return gcdHelper(y, x);
} else {
return gcdHelper(y, x % y);
}
}
Another translation example.
Notice that both of the parameters are kinds of accumulators. Let’s translate this into a loop.
What’s great about the pipeline is that, even if the method doesn’t make sense to us, we can always mechanically translate from tail recursion to loops.
static int gcdHelper(int x, int y) {
int x1 = x;
int y1 = y;
while (!(y1 == 0)) {
if (y1 > x1) {
int tmp = x1;
x1 = y1;
y1 = tmp;
} else {
int tmp = x1;
x1 = y1;
y1 = tmp % y1;
}
}
return x1;
}
Writing loops without the pipeline.
Let’s write some loops without translating from recursion!
Example: Design the int countChars(String s, char c) method that returns the number of times c occurs in s.
Writing loops without the pipeline.
We could use a while loop, but that’s not necessary.
for loops are for known loop bounds.
In this case, we know strings are indexed from 0 to |S|-1.
static int countChars(String s, char c) {
int counter = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == c) {
counter++;
}
}
return counter;
}
Writing loops without the pipeline.
For loops encapsulate three components:
For loops are equivalent to while loops.
Note that i++ is i = i + 1 or i += 1.
static int countChars(String s, char c) {
int counter = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == c) {
counter++;
}
}
return counter;
}
for loop syntax.
Loops can contain multiple variable declarations.
for (int i = 0, j < 0; i < 100 && j < 200; i++, j += 2) {
…
}
What variables are declared in the loop?
What condition is true when the loop ends?
What are the changes of i, j in the loop?
for loop syntax.
for (int i = 0, j < 0; i < 100 && j < 200; i++, j += 2) {
…
}
The updates/steppers take place in the given order and are executed after the body evaluates. Then, the loop returns to the top, in which the condition is re-checked.
Does this loop ever execute?
for (int i = 100; i < 10; i--) {
…
}
break and continue.
We can break out of a loop using break. We can stop the execution of remaining body code using continue.
static int foo(int n){ � int c = 0;
for (int i = n; i >= 0; i--) {
if (n % 5 == 0) {
continue;
} else {
break;
}
c++;
}
return c;
}
What does foo(50) return?
i = 50 -> continue ∴ c = 0
49 -> c++ ∴ c = 1
48 -> c++ ∴ c = 2
47 -> c++ ∴ c = 3
46 -> continue ∴ c = 4
45 -> continue ∴ c = 4
44 -> c++ ∴ c = 5
43 -> c++ ∴ c = 6
42 -> break ∴ done.
∴ foo(50) => 6
Nested for loops
You can also nest for loops!
What does the following code output for compute(3, 4)?
Example: use two loops to compute intermediate products.
static int compute(int m, int n) {
int s = 0;
for (int i = 1; i <= m; i++) {� for (int j = 1; j <= n; j++) {
s += i * j;
}
}
return s;
}
60
Nested for loops
compute(3, 4):
s = 1, i = 1, j = 1
s = 3, i = 1, j = 2
s = 6, i = 1, j = 3
s = 10, i = 1, j = 4
s = 12, i = 2, j = 1
s = 16, i = 2, j = 2
s = 22, i = 2, j = 3
s = 30, i = 2, j = 4
s = 33, i = 3, j = 1
s = 39, i = 3, j = 2
s = 48, i = 3, j = 3
s = 60, i = 3, j = 4
Example: use two loops to compute intermediate products.
static int compute(int m, int n) {
int s = 0;
for (int i = 1; i <= m; i++) {� for (int j = 1; j <= n; j++) {
s += i * j;
}
}
return s;
}
Loops “versus” recursion.
In general, once you get good at translating tail recursive methods to loops, you can just use loops.
This is not to say that recursion has no place - it ABSOLUTELY does!
Java is an imperative language, meaning loops are more commonplace.