Recursion Test Questions & Answers Chapter.17

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).

3) Write a recursive method that computes the sum of the first n integers.

4) Write the recursive definition of the factorial of a number.

5) Write a recursive method that returns the factorial of an integer.

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.

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.

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?

12) Describe a recursive solution to the Towers of Hanoi puzzle with N disks.

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.

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).