Deck 16: Recursion

Question 1

To solve a program recursively, you need to identify at least one case in which the problem can be solved without recursion - this is known as the:

A) recursive case
B) terminal case
C) base case
D) final case

Answer 1

C

Question 2

Look at the following pseudocode algorithm: algorithm Test14(int x)
If (x < 8)
Return (2 * x)
Else
Return (3 * Test14(x - 8) + 8)
End Test14
What is the depth of Test14(16)?

A) 0
B) 1
C) 2
D) 3

Answer 2

C

Question 3

Look at the following method: public static int test2(int x, int y)
{
If ( x < y)
{
Return -5;
}
Else
{
Return (test2(x - y, y + 5) + 6);
}
}
What is the depth of test2(18,5)?

A) 0
B) 1
C) 2
D) 3

Answer 3

C

Question 4

Look at the following pseudocode algorithm: algorithm Test14(int x)
If (x < 8)
Return (2 * x)
Else
Return (3 * Test14(x - 8) + 8)
End Test14
What is the recursive case for the algorithm?

A) x < 8
B) 2 * x
C) x != 8
D) x >= 8

Question 5

Look at the following pseudocode algorithm: algorithm Test14(int x)
If (x < 8)
Return (2 * x)
Else
Return (3 * Test14(x - 8) + 8)
End Test14
What is the depth of Test14(7)?

A) 0
B) 1
C) 6
D) 7

Question 6

Look at the following method: public static int test2(int x, int y)
{
If ( x < y)
{
Return -5;
}
Else
{
Return (test2(x - y, y + 5) + 6);
}
}
What is returned for test2(10, 20)?

A) 6
B) 10
C) 1
D) -5

Question 7

Look at the following method: public static int test2(int x, int y)
{
If ( x < y)
{
Return -5;
}
Else
{
Return (test2(x - y, y + 5) + 6);
}
}
What is the recursive case for the method?

A) x < y
B) -5
C) x >= y
D) x != y

Question 8

Look at the following pseudocode algorithm: algorithm Test14(int x)
If (x < 8)
Return (2 * x)
Else
Return (3 * Test14(x - 8) + 8)
End Test14
What value is returned for Test14(7)?

A) 0
B) 7
C) 14
D) -5

Question 9

Recursion can be a powerful tool for solving:

A) basic problems
B) repetitive problems
C) object-oriented problems
D) binary problems

Question 10

Usually, a problem is reduced by making the value of one or more parameters ________ with each recursive call.

A) larger
B) smaller
C) negative
D) equal

Question 11

Recursive algorithms are usually less efficient than:

A) iterative algorithms
B) quantum algorithms
C) pseudocode algorithms
D) none of the above

Question 12

Like a loop, a recursive method must have:

A) a counter
B) some way to control the number of times it repeats itself
C) a return statement
D) a predetermined number of times it will execute before terminating

Question 13

How many times will the following method call itself if the value 10 is passed as an argument?
Public static void message(int n)
{
If (n > 0)
{
System.out.println("Print this line.\n");
Message(n + 1);
}
}

A) 1
B) 9
C) 10
D) An infinite number of times

Question 14

Look at the following method: public static int test2(int x, int y)
{
If ( x < y)
{
Return -5;
}
Else
{
Return (test2(x - y, y + 5) + 6);
}
}
What is returned for test2(18,5)?

A) 6
B) -5
C) 7
D) 1

Question 15

Look at the following pseudocode algorithm: algorithm Test14(int x)
If (x < 8)
Return (2 * x)
Else
Return (3 * Test14(x - 8) + 8)
End Test14
What value is returned for Test14(16)?

A) 8
B) 16
C) 24
D) 32

Question 16

The depth of recursion is:

A) the number of times that a method calls itself
B) the value returned from the last recursive call
C) the value that will terminate the recursive calls
D) The order in which the method appears on the stack

Question 17

A recursive method is:

A) a method that accepts no arguments
B) a method that contains a static field
C) a method that calls itself
D) a method that has a loop

Question 18

The actions that the JVM must perform any time a method is called are known as:

A) Stack depth
B) Overhead
C) Housekeeping
D) Method calls

Question 19

Look at the following method: public static int Test2(int x, int y)
{
If ( x < y)
{
Return -5;
}
Else
{
Return (Test2(x - y, y + 5) + 6);
}
}
What is the base case for the method?

A) x < y
B) -5
C) Test2(x - y, y + 5) + 6
D) +6

Question 20

Look at the following pseudocode algorithm: algorithm Test14(int x)
If (x < 8)
Return (2 * x)
Else
Return (3 * Test14(x - 8) + 8)
End Test14
What is the base case for the algorithm?

A) x < 8
B) 2 * x
C) 3 * Test14(x - 8) + 8
D) x >= 8

Question 21

Indirect recursion occurs when:

A) a loop is used to solve a recursive problem
B) a recursive method has no code to stop it from repeating
C) a method calls itself
D) a method calls itself from another method

Question 22

A problem can be solved recursively if it can be broken down into successive smaller problems that are unique within the overall problem.

Question 23

Look at the following pseudocode algorithm: Algorithm gcd(x, y)
If (x < y)
Gcd (y, x)
Else
If (y = 0)
Return x
Else
Return gcd(y, x mod y)
End gcd
What is returned from gcd(60, 24)?

A) 60
B) 24
C) 12
D) 66

Question 24

Look at the following pseudocode algorithm: Algorithm Test3(int a, int b)
If (a < b)
Return 5
Else if ( a == b)
Return -5;
Else
Return (a + Test3(a - 1, b)
End Test3
What is the base case for the algorithm?

A) a < b
B) a == b
C) Both A and B
D) neither A nor B

Question 25

If the base case in a recursive method is never reached:

A) the method will call itself only once
B) the result will always be off by one
C) the method will call itself indefinitely
D) the method will never call itself

Question 26

The Towers of Hanoi is:

A) a mathematical game
B) often used in computer science textbooks
C) demonstrates the power of recursion
D) all of the above

Question 27

The number of times that a method calls itself is known as the:

A) height of recursion
B) depth of recursion
C) width of recursion
D) length of recursion

Question 28

Any problem that can be solved recursively can also be solved iteratively.

Question 29

How many times will the following method call itself if the value 10 is passed as the argument?
Public static void message(int n)
{
If (n < 0)
{
System.out.println("Print this line.\n");
Message(n + 1);
}
}

A) 0
B) 9
C) 10
D) An infinite number of times

Question 30

Look at the following pseudocode algorithm: Algorithm Test3(int a, int b)
If (a < b)
Return 5
Else if ( a == b)
Return -5;
Else
Return (a + Test3(a - 1, b)
End Test3
What is the recursive case for the algorithm?

A) a < b
B) a == b
C) a > b
D) None of the above

Question 31

This type of method is a method that calls itself.

A) Looping
B) Circular
C) Recursive
D) Reoccurring

Question 32

Indirect recursion occurs when a method calls another method that in turn calls the first method.

Question 33

Look at the following pseudocode algorithm: Algorithm gcd(x, y)
If (x < y)
Gcd (y, x)
Else
If (y = 0)
Return x
Else
Return gcd(y, x mod y)
End gcd
What is the base case for the algorithm gcd?

A) x < y
B) y == 0
C) x == 0
D) y > x

Question 34

Which of the following problems can be programmed recursively?

A) Towers of Hanoi
B) Quicksort
C) Binary search
D) All of the above

Question 35

This term is used for methods that directly call themselves.

A) Direct recursion
B) Simple recursion
C) Absolute recursion
D) Native recursion

Question 36

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

Question 37

Recursive algorithms are usually less efficient than iterative algorithms.

Question 38

The part of a problem that is solved with recursion is known as the:

A) terminal case
B) final case
C) absolute case
D) recursive case

Question 39

Like ________, a recursive method must have some way to control the number of times it repeats.

A) a loop
B) any method
C) a class constructor
D) an event

Question 40

Unlike a loop, a recursive method does not require code to stop it from repeating.

Question 41

If method A calls method B, which in turn calls method A, it is called indirect recursion.

Question 42

A problem can be solved recursively if it can be broken down into successive smaller problems that are identical to the overall problem.