Question 1

The recursive solution of the Towers of Hanoi problem has _______________ complexity.
A) exponential
B) polynomial
C) logarithmic
D) low
E) none of the above

Accepted Answer

The recursive solution of the Towers of Hanoi problem has exponential complexity, which means that it is significantly inefficient.

Question 2

A method that calls itself is a __________________ method.
A) invalid
B) static
C) final
D) recursive
E) public

Accepted Answer

A recursive method is a method that calls itself.

Question 3

Which of the following is a proper recursive definition of x raised to the y power? A) x^y = x*x^y-1 B) x^y = x*x^y-2 C) x^y = x*x^y-1 for y > 1; x^y = x for y = 1 D) x^y = x*x^y-1for all x E) none of the above

Accepted Answer

Choice c is correct because it has a properly defined base case.

Question 4

A method that calls a different method, which then calls the original calling method is a recursive method.

Accepted Answer

This is an example of indirect recursion.

Question 5

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.

Accepted Answer

Recursion should be used when the solution is easily expressed recursively.

Question 6

In the Towers of Hanoi puzzle __________________________________ .
A) it is legal to move a disk onto a peg that contains smaller disks.
B) it is legal to sit a disk aside, not on any peg.
C) it is illegal to move a disk onto a peg that contains only larger disks.
D) it is illegal to move a disk onto a peg that contains no other disks.
E) none of the above are true

Accepted Answer

Neither choice a, choice b, choice c, or choice d make the statement true.

Question 7

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

Accepted Answer

A base case is always necessary in a recursive solution to avoid infinite recursion.

Question 8

A solution with exponential complexity is ____________________ .
A) efficient
B) inefficient
C) easy to implement
D) difficult to implement
E) none of the above

Accepted Answer

A solution with exponential complexity is very inefficient.

Question 9

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

Accepted Answer

In the Towers of Hanoi puzzle, there are always exactly three pegs.

Question 10

All recursive methods must have a base case.

Accepted Answer

If a recursive method does not have a base case, it will yield an infinite recursion which will crash a program.

Question 11

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.

Accepted Answer

All recursive programs can be implemented iteratively, although a recursive solution may be easier to code.

Question 12

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

Accepted Answer

There are two base cases in the recursive solution to this problem. The two base cases are: (1) a path has been found, and (2) there is no way to move forward via the current path.

Question 13

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.

Accepted Answer

Infinite recursion will cause a program to run out of memory.

Question 14

In Java, it is possible for a method to call itself.

Accepted Answer

A method that calls itself is a recursive method.

Question 15

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

Accepted Answer

The Tower of Hanoi puzzle has an elegant recursive solution, and has therefore become a favorite of computer scientists.

Question 16

____________________ 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

Accepted Answer

Direct recursion occurs when a method calls itself, while indirect recursion occurs when a method calls another method that then calls the original method.

Question 17

Some problems can only be solved recursively.

Accepted Answer

Since it is possible to simulate recursion using an iterative program, any problem that can be solved recursively can also be solved iteratively.

Question 18

__________________ recursion results from the lack of a base case.
A) Indirect
B) Direct
C) Infinite
D) Spiral
E) none of the above

Accepted Answer

Infinite recursion results from the lack of a base case, which causes the recursive path to be followed forever.

Question 19

In the Towers of Hanoi puzzle there are __________________ disks of different diameters.
A) 2
B) 3
C) 4
D) 5
E) The Towers of Hanoi puzzle can include any number of disks of different diameters.

Accepted Answer

There can be any number of disks in the Towers of Hanoi puzzle.

Question 20

Recursive solutions to problems should be used whenever possible.

Accepted Answer

There are some cases where the iterative solution is much less complex and more straighforward to code. In these cases, recursion is not the best choice.

Quiz 11: Recursion

The recursive solution of the Towers of Hanoi problem has _______________ complexity.

A method that calls itself is a __________________ method.

Which of the following is a proper recursive definition of x raised to the y power?

A method that calls a different method, which then calls the original calling method is a recursive method.

Which of the following statements is true?

In the Towers of Hanoi puzzle __________________________________ .

In a recursive solution, _______________ is(are) always necessary.

A solution with exponential complexity is ____________________ .

In the Towers of Hanoi puzzle, there are ________________ pegs.

All recursive methods must have a base case.

All recursive programs ____________________________________ .

There is(are) ____________ base case(s) in the recursive solution to finding a path through a maze.

Which of the following will result from infinite recursion in Java?

In Java, it is possible for a method to call itself.

The _______________________ puzzle is a favorite of computer scientists because of its elegant recursive solution.

____ recursion occurs when a method calls itself, while _ recursion when a method calls another method that then calls the original method.

Some problems can only be solved recursively.

__________________ recursion results from the lack of a base case.

In the Towers of Hanoi puzzle there are __________________ disks of different diameters.

Recursive solutions to problems should be used whenever possible.