CIS 255 Recursion

Question 1

A recursive solution can always be rewritten with iteration. And an iterative solution can always be rewritten with recursion. (True or False)

Question 2

Code that contains an infinite recursion will result in __________.

Question 3

Why might the following method have infinite recursion?

public int infiniteRecursion(int n) {
if (n > 0) {
return infiniteRecursion(n) - 2;
} else {
return 0;
}
}

Question 4

Why might the following method have infinite recursion?

public void infiniteRecursion(int n) {
if (n > 0) {
System.out.println("here");
infiniteRecursion(n-1);
} else if(n < 0){
System.out.println("here");
infiniteRecursion(n+1);
} else {
System.out.println("here");
}
}

Question 5

What condition of the parameters will cause the following method to have infinite recursion?

public int secretMethod(int x, int y) {
if (x == y) {
return 1;
} else {
return secretMethod(x-1, y) + 1;
}
}

Question 6

The following method lacks a base case. (True or False)

public int noBaseCasePerhaps(int x) {
if (x > 0) {
return noBaseCasePerhaps(x–1) + 1;
} else {
return noBaseCasePerhaps(x–2) + 2;
}
}

Question 7

What does the following recursive method determine if initially invoked with j=0?

public boolean whoKnows(int[]a, int[] b, int j) {
if (j == a.length) {
return true;
} else if (j == b.length) {
return false;
} else {
return whoKnows(a, b, j+1);
}
}

Question 8

The following two methods will both compute the same thing when invoked with the same value of x. That is, method1(x) == method2(x). (True or False)

public int method1(int x) {
if (x > 0) {
return method1(x–1) + 1;
} else {
return 0;
}
}

public int method2(int x) {
if (x <= 0) {
return 0;
} else {
return 1 + method2(x–1);
}
}

Question 9

The following method is designed to count the number of even numbers in an array.

public int countEvens(int[] array) {
return countEvensHelper(array, 0, array.length);
}

private int countEvensHelper(int[] array, int start, int stop) {
int count = 0;
if(start==stop) {
return count;
} else {
if(array[start] % 2 == 0) {
count = 1 + countEvensHelper(array, start+1, stop);
}
return count;
}
}

Which of the following is true if the method is invoked with a non-empty array?

• The code is correct.
• The code will run, but then will either crash or go into infinite recursion.
• The code will run, but there is a logical error.
• There is a compiler (syntax) error.
• none of these are correct

Question 10

The following method is designed to count the number of odd numbers in an array.

public int countOdds(int[] array) {
return countOddsHelper(array, 0, array.length);
}

private int countOddsHelper(int[] array, int start, int stop) {
int count = 0;
if(start < stop) {
if(array[start] % 2 == 1) {
count++;
}
countOddsHelper(array, start+1, stop);
}
return count;
}

Which of the following is true if the method is invoked with a non-empty array?

• The code will run, but there is a logical error.
• The code will run, but then will either crash or go into infinite recursion.
• none of these is correct
• one of these is correct
• There is a compiler (syntax) error.

Question 11

The following method is designed to count the number of zeros in an array.

public int countZeros(int[] array) {
return countZerosHelper(array, 0, array.length, 0);
}

private int countZerosHelper(int[] array, int start, int stop, int count) {
if(start < stop) {
if(array[start] == 0) {
count++;
}
countZerosHelper(array, start+1, stop, count);
}
return count;
}

Which of the following is true if the method is invoked with a non-empty array?

• Which of the following is true if the method is invoked with a non-empty array?
• The code is correct.
• The code will run, but then will either crash or go into infinite recursion.
• There is a compiler (syntax) error.
• The code will run, but there is a logical error.

Question 12

The following method will return true if the int parameter is even and non-negative (meaning positive or 0), and false otherwise. For example, invoking with 0, 2, 4, 6, or 8 will return true. Invoking with -4, -3, -2, -1, 1, 3, 5, or 7 will return false.

Which set of code should be added so that the method works appropriately?

public boolean evenPosZero(int x) {
if(x<0)
return false;

// ??? what goes here

}

For the next set of questions, use the following method.

public int methodA(int n) {
if(n==0) {
return 0;
} else if(n>0) {
return 1 + methodA(n-1);
} else {
return 1 + methodA(n+1);
}
}

Question 13

What is the value returned from invoking methodA(4)?

Question 14

What is the value returned from invoking methodA(0)?

Question 15

What is the value returned from invoking methodA(-3)?

For the next set of questions, use the following method.

public int methodB(String s, char c) {
if(s.length()==0) {
return 0;
} else {
return (s.charAt(0)==c ? 1 : 0) + methodB(s.substring(1), c);
}
}

Question 16

What is the value returned from invoking methodB("eieio",'e')?

Question 17

What is the value returned from invoking methodB("hello there",'h')?

For the next set of questions, assume that int[] a = {3, 4, 2, 5, 7, 3, 2, 5, 3} and consider the two recursive methods below foo and bar.

public int foo(int[] a, int b, int j) {
if (j < a.length) {
if (a[j] == b) {
return foo (a, b, j+1);
} else {
return foo (a, b, j+1) + 1;
}
} else {
return 0;
}
}

public int bar(int[] a, int j) {
if (j < a.length) {
return a[j] + bar(a, j+1);
} else {
return 1;
}
}

Question 18

What is the result of calling foo(a, 3, 4);?

Question 19

What is the result of calling foo(a, 3, 0);?

Question 20

What is the result of calling bar(a, 6);?

Question 21

What is the result of calling bar(a, 9);?

The next set of questions asks about the following recursive method, described in pseudocode.

I recommend you trace out this method and have the output on hand to answer the questions.

public void recMethod(int[] array, int start, int end) {

if(start < end) {
print the array

double the value in the array at position start

recMethod(array, start+1, end)

print the array

} else {
print "done"
}
}

Assume the method is invoked with array = [3, 4, 6, 7, 8, 10, 4], start = 2, and end = 5.

Question 22

How many times is the array printed before the word "done" is printed?

Question 23

How many times is the array printed after the word "done" is printed?

Question 24

Which of the following is true?

• There is nothing printed out after the "done."
• The contents printed in the line directly before the "done" are different from the contents printed in the line directly after the "done."
• The contents printed in the line directly before the "done" are the same as the contents printed in the line directly after the "done."

Question 25

Which of the following is true?

• There are no array print outs after the "done."
• All array print outs after the "done" show the same contents as each other.
• The array print outs after the "done" are not all the same.

Question 26

Assume that the method is invoked with array = [1, 4, 6, 3, 2, 7, 8], start = 3, and end = 2.

Which of the following is true?

• there will be 0 lines of output (and no exceptions)
• there will be 1 line of output (and no exceptions)
• an exception or error is thrown
• none of these is correct
• there will be 2 lines of output (and no exceptions)

Question 27

Assume that the method is invoked with array = [1, 4, 6, 3, 2, 7, 8], start = 3, and end = 8.

Which of the following is true?

• there will be 0 lines of output (and no exceptions)
• there will be 2 lines of output (and no exceptions)
• there will be 1 line of output (and no exceptions)
• none of these is correct
• an exception or error is thrown

Question 28

Write a recursive void method that reverses the contents of an array. Do not create a new array- reverse the contents of the current array.

The method header is:

public static void reverseArray(int[] array)

Question 29

Write a recursive method to determine whether a String contains a 'q' not immediately followed by a 'u' (ignoring capitalization).

Carefully review the provided driver program to see example test cases.

For full credit, do not use the String methods contains, indexOf, lastIndexOf, matches, or split.

The method header is:

public static boolean qNotFollowedByU(String word)

HomeworkM13Driver

import java.util.*;

public class HomeworkM13Driver {

public static void main(String[] args) {

System.out.println("******TESTING Q WITHOUT U");
System.out.println("\nAll of these should be false. They do NOT contain a \"q\" that is not immediately followed by a \"u\"");
System.out.println("hello: \t\tfalse: " + qNotFollowedByU("hello")); // no q at all- odd length
System.out.println("cats: \t\tfalse: " + qNotFollowedByU("cats")); // no q at all- even length
System.out.println("a: \t\tfalse: " + qNotFollowedByU("a")); // no q at all- single letter
System.out.println("quite: \t\tfalse: " + qNotFollowedByU("quite")); // q followed by u at the beginning
System.out.println("equal: \t\tfalse: " + qNotFollowedByU("equal")); // q followed by u in the middle- odd length
System.out.println("aqua: \t\tfalse: " + qNotFollowedByU("aqua")); // q followed by u in the middle- even length
System.out.println("nonsensewordqu: false: " + qNotFollowedByU("nonsensewordqu")); // q followed by u at the end
System.out.println("QUOTE: \t\tfalse: " + qNotFollowedByU("QUOTE")); // q followed by u in caps
System.out.println("qu: \t\tfalse: " + qNotFollowedByU("qu")); // q followed by u and nothing else
System.out.println("\"\": \t\tfalse: " + qNotFollowedByU("")); // empty string

System.out.println("\nAll of these should be true. They DO contain a \"q\" that is not immediately followed by a \"u\"");
System.out.println("qat: \t\ttrue: " + qNotFollowedByU("qat")); // q without u at the beginning
System.out.println("cinq: \t\ttrue: " + qNotFollowedByU("cinq")); // q without u at the end- even length
System.out.println("drinq: \t\ttrue: " + qNotFollowedByU("drinq")); // q without u at the end- odd length
System.out.println("nonsenseqword: \ttrue: " + qNotFollowedByU("nonsenseqword")); // q without u in the middle
System.out.println("aquaq: \t\ttrue: " + qNotFollowedByU("aquaq")); // q without u in a word that also has a "qu" before it
System.out.println("qaqu: \t\ttrue: " + qNotFollowedByU("qaqu")); // q without u in a word that also has a "qu" after it
System.out.println("qiteu: \t\ttrue: " + qNotFollowedByU("qiteu")); // q without u right after, but with a u later on
System.out.println("q: \t\ttrue: " + qNotFollowedByU("q")); // q all on its own- single letter
System.out.println("qq: \t\ttrue: " + qNotFollowedByU("qq")); // q all on its own- double letter
System.out.println("uq: \t\ttrue: " + qNotFollowedByU("uq")); // q with a u before it
System.out.println("Qtip: \t\ttrue: " + qNotFollowedByU("Qtip")); // q without a u in caps

System.out.println("\n******TESTING ARRAY REVERSER");
int[] array1 = {1, 2, 3, 4, 5};
System.out.println("Before reverse: " + Arrays.toString(array1));
System.out.println("After reverse should be");
printReverse(array1);
reverseArray(array1);
System.out.println(Arrays.toString(array1));
System.out.println("After reversing back should be");
printReverse(array1);
reverseArray(array1);
System.out.println(Arrays.toString(array1));

int[] array2 = {1, 2, 3, 4, 5, 6};
System.out.println("\nBefore reverse: " + Arrays.toString(array2));
System.out.println("After reverse should be");
printReverse(array2);
reverseArray(array2);
System.out.println(Arrays.toString(array2));
System.out.println("After reversing back should be");
printReverse(array2);
reverseArray(array2);
System.out.println(Arrays.toString(array2));

int[] array3 = {1, 2};
System.out.println("\nBefore reverse: " + Arrays.toString(array3));
System.out.println("After reverse should be");
printReverse(array3);
reverseArray(array3);
System.out.println(Arrays.toString(array3));

int[] array4 = {1};
System.out.println("\nBefore reverse: " + Arrays.toString(array4));
System.out.println("After reverse should be");
printReverse(array4);
reverseArray(array4);
System.out.println(Arrays.toString(array4));

int[] array5 = {};
System.out.println("\nBefore reverse: " + Arrays.toString(array5));
System.out.println("After reverse should be");
printReverse(array5);
reverseArray(array5);
System.out.println(Arrays.toString(array5));


}

public static boolean qNotFollowedByU(String word) {
word = word.toLowerCase();

if (word.isEmpty() || !word.contains("q")) {
return false;
}

if (word.contains("qu")) {
return qNotFollowedByU(word.replace("qu", ""));
}

return true;
}


public static void reverseArray(int[] array) {
if (array.length == 2) {
int temp = array[0];
array[0] = array[1];
array[1] = temp;
} else if (array.length > 2) {
int first = array[0];
array[0] = array[array.length - 1];
array[array.length - 1] = first;

int[] newArray = new int[array.length - 2];
System.arraycopy(array, 1, newArray, 0, array.length - 2);
reverseArray(newArray);
System.arraycopy(newArray, 0, array, 1, newArray.length);
}
}

// a printing method for testing purposes
public static void printReverse(int[] array) {
System.out.print("[");
for(int i=array.length-1; i>0; i--) {
System.out.print(array[i] + ", ");
}
if(array.length>0) {
System.out.print(array[0]);
}
System.out.println("]");
}
}