Ch17 Exam Questions Recursion - Instructor Test Bank | Java Foundations 5e Lewis by John Lewis. DOCX document preview.
Chapter 17: Recursion
Multiple Choice Questions:
1) A method that calls itself is a __________________ method.
a) invalid
b) static
c) final
d) recursive
e) public
2) ____________________ recursion occurs when a method calls itself, while _________________ recursion when a method calls another method that then calls the original method.
a) upward, downward
b) downward, upward
c) direct, indirect
d) indirect, direct
e) none of the above
3) __________________ recursion results from the lack of a base case.
a) Indirect
b) Direct
c) Infinite
d) Spiral
e) none of the above
4) The _______________________ puzzle is a favorite of computer scientists because of its elegant recursive solution.
a) Tower of Hanoi
b) Sudoku
c) Tetris
d) Tic-Tac-Toe
e) none of the above
5) In the Towers of Hanoi puzzle, there are ________________ pegs.
a) 2
b) 3
c) 4
d) 5
e) The Towers of Hanoi puzzle can include any number of pegs
6) In indirect recursion, how many method calls can occur between one call to a method and the next one that completes the indirect recursion
a) 2
b) 3
c) 4
d) 5
e) There is no limit to the number of intervening calls between a method and its indirect recursive call.
7) Which of the following statements is true?
a) Recursion should be used in every program.
b) Recursion should be avoided all the time.
c) Solutions that are easily expressed recursively should be programmed recursively.
d) Solutions that are easily expressed recursively should be programmed iteratively.
e) None of the above.
8) Which of the following will result from infinite recursion in Java?
a) The program will hang as though there is an infinite loop.
b) The program will throw an ArrayOutOfBoundsException.
c) The program will not compile.
d) The program will run out of memory.
e) none of the above.
9) How many base cases must a recursive method have?
a) A recursive method does not have to have a base case.
b) at least 1
c) more than 1
d) more than 2
e) more than 3
10) All recursive programs ____________________________________ .
a) are more difficult to read than iterative programs.
b) can be implemented iteratively.
c) are easier to read than iterative programs.
d) are shorter than iterative programs.
e) none of the above are true.
11) The recursive solution of the Towers of Hanoi problem has _______________ complexity.
a) exponential
b) polynomial
c) logarithmic
d) low
e) none of the above
12) Which of the following is a proper recursive definition of x raised to the y power?
a)
b)
c)
d)
e) none of the above
13) There is(are) ____________ base case(s) in the recursive solution to finding a path through a maze.
a) 0
b) 1
c) 2
d) 3
e) 4
14) A solution with exponential complexity is ____________________ .
a) efficient
b) inefficient
c) easy to implement
d) difficult to implement
e) none of the above
15) In a recursive solution, _______________ is(are) always necessary.
a) short, efficient code
b) several variables
c) numerous lines of code
d) a base case
e) none of the above
1) In Java, it is possible for a method to call itself.
2) Some problems can only be solved recursively.
3) All recursive methods must have a base case.
4) A method that calls a different method, which then calls the original calling method is a recursive method.
5) Recursive solutions to problems should be used whenever possible.
6) In the Towers of Hanoi puzzle, it is legal to move a larger disk to a peg that already contains a smaller disk.
7) The Towers of Hanoi puzzle cannot be solved iteratively.
8) Determining whether or not there is a path through a maze has a recursive solution.
9) A program with infinite recursion will act similarly to a program with an infinite loop.
10) Recursive solutions are always more efficient than iterative solutions
1) What is recursion?
2) Give a recursive definition of the sum of the first n integers, S(n).
S(0) = 0
S(n) = n + S(n – 1) for n > 0
3) Write a recursive method that computes the sum of the first n integers.
public int sum(int n)
{
if(n == 0)
return 0;
else
return n + sum(n-1);
}
4) Write the recursive definition of the factorial of a number.
5) Write a recursive method that returns the factorial of an integer.
public int factorial(int n)
{
if(n == 0)
return 1;
else
return n*factorial(n-1);
}
6) What is wrong with the following recursive method that computes the sum of all of the odd positive integers less than or equal to n?
public int sumOfOdds(int n)
{
if(n%2 == 0)
return sumOfOdds(n-1);
else
return n + sumOfOdds(n-2);
}
7) Write a recursive definition for K(n), which represents the product of all of the even integers less than or equal to n.
8) Write a recursive method that computes the product of all of the even integers less than or equal to n.
public int productOfEvens(int n)
{
if(n <= 1)
return 0;
if(n == 2)
return 2;
if(n%2 == 0)
return n*productOfEvens(n-2);
else
return productOfEvens(n-1);
}
9) The Fibonacci sequence is defined as the sequence that begins with 0 and 1, and every other number in the sequence is the sum of the two preceding numbers. Write a recursive mathematical definition of the numbers in the Fibonacci sequence.
10) The Fibonacci sequence is defined as the sequence that begins with 0 and 1, and every other number in the sequence is the sum of the two preceding numbers. Write a recursive method that computes the number in the Fibonacci sequence.
public int fibonacci(int n)
{
if(n == 1) return 0;
if(n == 2) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
9) The Lucas sequence is defined as the sequence that begins with 2 and 1, and every other number in the sequence is the sum of the two preceding numbers. A recursive method to generate the term in the Lucas sequence is:
public int lucas(int n)
{
if(n == 1) return 2;
if(n == 2) return 1;
return lucas(n-1) + lucas(n-2);
}
When calculating lucas(8), how many times is lucas(5) calculated?
lucas(8)
/ \
lucas(7) lucas(6)
/ \ / \
lucas(6) lucas(5) lucas(5) lucas(4)
/ \
lucas(5) lucas(4)
There are 3 calls to lucas(5), so lucas (5) is calculated 3 times in the calculation of lucas(8).
12) Describe a recursive solution to the Towers of Hanoi puzzle with N disks.
(1) Move the top N-1 disks to the extra peg.
(2) Move the largest disk from the original peg to the destination peg.
(3) Move the N-1 disks from the extra peg to the destination peg.
The first step is the same problem again, with the extra peg and the destination peg interchanged, and therefore this subproblem can be solved recursively. The base case is when N = 1, in which case we simply move the disk without any recursive call.
13) What is/are the base case(s) when calculating the sum of the first n positive integers recursively?
14) Describe a recursive solution to determine whether a String object is a palindrome. You may assume that the string only contains lower case characters (i.e. no numbers, spaces, punctuation, etc.). Hint: It may be easiest to describe your solution using pseudocode.
isPalindrome(String s)
if the length of the string is 1
return true
else if the length of the string is 2 and the two characters are the same
return true
else if the first and the last characters are the same
return isPalindrome(the string created by removing the first and last characters)
else
return false
15) Write a recursive Java method that takes a String as a parameter and returns true if the String is a palindrome. You may assume that the string only contains lower case characters (i.e. no numbers, spaces, punctuation, etc).
public boolean isPalindrome(String s) {
if(s.length() == 1)
return true;
else if(s.length() == 2 && s.charAt(0) == s.charAt(1))
return true;
else if(s.charAt(0) == s.charAt(s.length() – 1))
return isPalindrome(s.substring(1, s.length() - 1));
else
return false;
}