Deck 11: Recursion

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

Answer 1

A
Explanation: 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

Answer 2

D
Explanation: 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-1 for all x
E) none of the above

Answer 3

C
Explanation: 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.

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.

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

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

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

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

Question 10

All recursive methods must have a base case.

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.

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

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.

Question 14

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

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

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

Question 17

Some problems can only be solved recursively.

Question 18

__________________ recursion results from the lack of a base case.

A) Indirect
B) Direct
C) Infinite
D) Spiral
E) none of the above

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.

Question 20

Recursive solutions to problems should be used whenever possible.

Question 21

Write a recursive definition for K(n), which represents the product of all of the even integers less than or equal to n.

Question 22

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

Question 23

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.

Question 24

Describe the Towers of Hanoi puzzle.

Question 25

The Towers of Hanoi puzzle cannot be solved iteratively.

Question 26

A program with infinite recursion will act similarly to a program with an infinite loop.

Question 27

What is recursion?

Question 28

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

Question 29

Write a recursive method that computes the product of all of the even integers less than or equal to n.

Question 30

Recursion is necessary.

Question 31

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);
}

Question 32

Write a recursive Java method that takes in 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).

Question 33

The Fibonacci sequence is defined as the sum of the two previous elements of the sequence, with the first and second numbers in the sequence being 0 and 1 respectively. Write a recursive method that computes the nth Fibonacci number.

Question 34

In the Towers of Hanoi puzzle, it is legal to move a larger disk to a peg that already contains a smaller disk.

Question 35

Write the recursive definition of the factorial of a number.

Question 36

Give a recursive definition of the sum of the first n integers, S(n).

Question 37

What are the "base" cases when searching for a path through a maze?

Question 38

Determining whether or not there is a path through a maze has a recursive solution.

Question 39

The Fibonacci sequence is defined as the sum of the two previous elements of the sequence, with the first and second numbers in the sequence being 0 and 1 respectively. Write a recursive mathematical definition of the Fibonacci numbers.

Question 40

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