FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 12: Recursion

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 21

Multiple Choice

Review LaterAdd Note

Review Later

For the questions below, refer to the following recursive factorial method. public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -What is returned if factorial(0) is called?

A) 0
B) 1
C) 2
D) nothing, factorial(0) causes infinite recursion
E) nothing, factorial(0) produces a run-time error

Correct Answer

verified

Show Answer

Question 22

Multiple Choice

Review LaterAdd Note

Review Later

Which of the following recursive methods would execute approximately log ₂ n times for an initial parameter n?

A) public void logcode(int n) {
If (n > 1) logcode(n - 1) ;
}
B) public void logcode(int n) {
If (n > 2) logcode(n - 2) ;
}
C) public void logcode(int n) {
If (n > 0) logcode(0) ;
}
D) public void logcode(int n) {
If (n > 1) logcode(n / 2) ;
}
E) public void logcode(int n) {
If (n > 1) logcode(n - 1 /2) ;
}

Correct Answer

verified

Show Answer

Question 23

Multiple Choice

Review LaterAdd Note

What does the following method compute? Assume the method is called initially with i = 0 Public int question9(String a, char b, int i) { If (i = = a.length( ) ) return 0; Else if (b = = a.charAt(i) ) return question9(a, b, i+1) + 1; Else return question9(a, b, i+1) ; }

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below. public boolean patternRecognizer(String a) { if (a == null) return false; else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True; else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false; else if (a.charAt(0) == a.charAt(a.length( ) - 1) ) return patternRecognizer(a.substring(1, a.length( ) - 1) ) ; else return false; } -Which String below would result in patternRecognizer returning True?

For the questions below, use the following recursive method. public int question1_2(int x, int y) { if (x == y) return 0; else return question1_2(x-1, y) + 1; } -The following method should return True if the int parameter is even and either positive or 0, and false otherwise. Which set of code should you use to replace ... so that the method works appropriately? Public boolean question3(int x) { ... }

Explain what a "base case" is in a recursive method.

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below. public boolean patternRecognizer(String a) { if (a == null) return false; else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True; else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false; else if (a.charAt(0) == a.charAt(a.length( ) - 1) ) return patternRecognizer(a.substring(1, a.length( ) - 1) ) ; else return false; } -If the method is called as patternRecognizer(x) where x is "aa", what will the result be?

As identified in the text, some algorithms execute only (approximately) log₂n operations if the original parameter or size of input is n. Compare this to an algorithm that executes n times by providing a table demonstrating the values of n and log₂n for n = 1, 10, 100, 1000, 10,000, 100,000 and 1,000,000.

Rewrite the following iterative method as a recursive method that computes the same thing. NOTE: your recursive method will require an extra parameter. public int iterative1(int x) { int count = 0, factor = 2; while (factor < x) { if (x % factor = = 0) count++; factor++; } return count; }

It always is possible to replace a recursion by an iteration and vice versa.

Demonstrate how factorial(4) is computed given the following recursive method for factorial: public int factorial(int n) { if (n > 1) return factorial(n - 1) * n; else return 1; }

We can define a list of int values recursively as: a list_item, followed by a comma, followed by a list where a list_item is any int value.

A Koch snowflake of order = 1 can be drawn without recursion.

Provide a definition for the terms as they relate to programming: recursion, indirect recursion and infinite recursion.

The Koch fractal of order 1 is

Rewrite the following iterative method as a recursive method that computes the same thing. NOTE: your recursive method will require an extra parameter. public String reversal(String x) { int y = x.length( ); String s = ""; for (int j = y-1; j >=0; j--) s += x.charAt(j); return s; }

Recursion is a popular programming tool but beginning programmers tend to shy away from it. Why do you suppose this is True?

For the questions below, use the following recursive method. public int question1_2(int x, int y) { if (x == y) return 0; else return question1_2(x-1, y) + 1; } -Calling this method will result in infinite recursion if which condition below is initially True?

The difference between direct and indirect recursion is

The game of high-low is one where one person selects a number between 1 and 100 and a user tries to guess it by guessing a number and being told if the guessed number is the right number, too low or too high. The user repeats guessing until getting the correct answer. A logical user will always guess at the midpoint of the possible values (for instance, the first guess is 50 followed by either 25 or 75, etc). Write a recursive method to play the game of high-low by having the computer guess a mid point. The method should receive three parameters, the number itself, the lowest value in the range and the highest value in the range and return the number of guesses that it took to guess the right number.