TEST BANK
INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES
1ST EDITION
CHAPTER NO. 1. RECURSION
1. What is the base case for a recursive function to compute xn?
a. x = 0
b. n = 0
c. xn = 0
d. x = 1
ANSWER: b
FEEDBACK: a. Incorrect. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0 (not x = 0). The base
case is determined by the value of n, not x.
b. Correct. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0.
c. Incorrect. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0 (not xn = 0). The base
case is determined by the value of n, not x.
d. Incorrect. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0 (not x = 1). The base
case is determined by the value of n, not x.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.1 - Describe the use of recursion in defining the power of a
number.
KEYWORDS: Bloom's: Understand
2. In tail recursion, which command in the function is the recursive call?
a. the first one
b. the last one
, c. the one with the base case condition
d. the one that is the sum of two terms
ANSWER: b
FEEDBACK: a. Incorrect. In tail recursion, the last (not the first) command in the
function is the recursive call. The returned value in the recursive
call case is only the recursive function.
b. Correct. In tail recursion, the last command in the function is the
recursive call. The returned value in the recursive call case is only
the recursive function.
c. Incorrect. In tail recursion, the last command in the function is the
recursive call, not the one with the base case condition. The base
case condition leads to a stopping point, not a recursive call.
d. Incorrect. In tail recursion, the last command in the function is the
recursive call. The returned value in the recursive call case is only
the recursive function. The function may or may not contain a
command that is the sum of two terms.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.2 - Recall the conditions of well-defined recursive functions
and procedures.
KEYWORDS: Bloom's: Remember
3. If recursion is not well-defined, it has no stopping case and will eventually result in a stack overflow error.
a. True
b. False
ANSWER: True
FEEDBACK: Correct Well-defined recursion is a term used to describe a recursive
algorithm that reaches an end state in a finite time and returns
the same value every time it is used. If recursion is not well-
defined, it has no stopping case and will eventually result in a
stack overflow error.
Incorrect Well-defined recursion is a term used to describe a recursive
algorithm that reaches an end state in a finite time and returns
the same value every time it is used. If recursion is not well-
defined, it has no stopping case and will eventually result in a
stack overflow error.
,POINTS: 1
DIFFICULTY: Intermediate
REFERENCES: Introduction to Recursion
QUESTION TYPE: True / False
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.3 - Associate the condition of well-defined recursion with a
stack overflow error.
KEYWORDS: Bloom's: Understand
4. What is the base case for a recursive function to compute n! (factorial of n)?
a. n2 = 1
b. n = 2
c. n = 1
d. n = 0
ANSWER: d
FEEDBACK: a. Incorrect. The base case for a recursive function to compute n! (factorial
of n) is n = 0 (not n2 = 1). The factorial of a non-negative integer n,
usually written as “n!”, is the product of all positive integers less than n.
Calculating the factorial of an integer does not involve squaring it.
b. Incorrect. The base case for a recursive function to compute n! (factorial
of n) is n = 0 (not n = 2). If n = 2, calculating the factorial of n will
require recursion: n * factorial(n - 1).
c. Incorrect. The base case for a recursive function to compute n! (factorial
of n) is n = 0 (not n = 1). If n = 1, calculating the factorial of n will
require recursion: n * factorial(n - 1).
d. Correct. The base case for a recursive function to compute n! (factorial
of n) is n = 0. The factorial of a non-negative integer n, usually written
as “n!”, is the product of all positive integers less than n.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.4 - Describe the relationship between recursion and the divide-
and-conquer strategy of problem-solving.
KEYWORDS: Bloom's: Understand
5. How many recursive calls are made in a recursive algorithm computing the Fibonacci sequence for n = 3?
, a. 3
b. 4
c. 5
d. 6
ANSWER: b
FEEDBACK: a. Incorrect. It requires 4 recursive calls, not 3. For a recursive function
fib, fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base
cases are n = 0 and n = 1, and making two recursive calls to the function
is necessary to compute a single number.
b. Correct. It requires 4 recursive calls. For a recursive function fib, fib(3)
calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base cases are n
= 0 and n = 1, and making two recursive calls to the function is
necessary to compute a single number.
c. Incorrect. It requires 4 recursive calls, not 5. For a recursive function
fib, fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base
cases are n = 0 and n = 1, and making two recursive calls to the function
is necessary to compute a single number.
d. Incorrect. It requires 4 recursive calls, not 6. For a recursive function
fib, fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base
cases are n = 0 and n = 1, and making two recursive calls to the function
is necessary to compute a single number.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.5 - Describe the use of tail recursion in recursive functions and
procedures.
KEYWORDS: Bloom's: Remember
6. Which term describes a recursive algorithm that reaches an end state in a finite time and returns the same
value every time it is used?
a. tail recursion
b. infinite recursion
c. well-defined recursion
d. stack overflow recursion
ANSWER: c
INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES
1ST EDITION
CHAPTER NO. 1. RECURSION
1. What is the base case for a recursive function to compute xn?
a. x = 0
b. n = 0
c. xn = 0
d. x = 1
ANSWER: b
FEEDBACK: a. Incorrect. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0 (not x = 0). The base
case is determined by the value of n, not x.
b. Correct. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0.
c. Incorrect. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0 (not xn = 0). The base
case is determined by the value of n, not x.
d. Incorrect. The first structure required in recursion is the base case, the
case in which the function will no longer call itself. For a recursive
function that computes xn, the base case is n = 0 (not x = 1). The base
case is determined by the value of n, not x.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.1 - Describe the use of recursion in defining the power of a
number.
KEYWORDS: Bloom's: Understand
2. In tail recursion, which command in the function is the recursive call?
a. the first one
b. the last one
, c. the one with the base case condition
d. the one that is the sum of two terms
ANSWER: b
FEEDBACK: a. Incorrect. In tail recursion, the last (not the first) command in the
function is the recursive call. The returned value in the recursive
call case is only the recursive function.
b. Correct. In tail recursion, the last command in the function is the
recursive call. The returned value in the recursive call case is only
the recursive function.
c. Incorrect. In tail recursion, the last command in the function is the
recursive call, not the one with the base case condition. The base
case condition leads to a stopping point, not a recursive call.
d. Incorrect. In tail recursion, the last command in the function is the
recursive call. The returned value in the recursive call case is only
the recursive function. The function may or may not contain a
command that is the sum of two terms.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.2 - Recall the conditions of well-defined recursive functions
and procedures.
KEYWORDS: Bloom's: Remember
3. If recursion is not well-defined, it has no stopping case and will eventually result in a stack overflow error.
a. True
b. False
ANSWER: True
FEEDBACK: Correct Well-defined recursion is a term used to describe a recursive
algorithm that reaches an end state in a finite time and returns
the same value every time it is used. If recursion is not well-
defined, it has no stopping case and will eventually result in a
stack overflow error.
Incorrect Well-defined recursion is a term used to describe a recursive
algorithm that reaches an end state in a finite time and returns
the same value every time it is used. If recursion is not well-
defined, it has no stopping case and will eventually result in a
stack overflow error.
,POINTS: 1
DIFFICULTY: Intermediate
REFERENCES: Introduction to Recursion
QUESTION TYPE: True / False
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.3 - Associate the condition of well-defined recursion with a
stack overflow error.
KEYWORDS: Bloom's: Understand
4. What is the base case for a recursive function to compute n! (factorial of n)?
a. n2 = 1
b. n = 2
c. n = 1
d. n = 0
ANSWER: d
FEEDBACK: a. Incorrect. The base case for a recursive function to compute n! (factorial
of n) is n = 0 (not n2 = 1). The factorial of a non-negative integer n,
usually written as “n!”, is the product of all positive integers less than n.
Calculating the factorial of an integer does not involve squaring it.
b. Incorrect. The base case for a recursive function to compute n! (factorial
of n) is n = 0 (not n = 2). If n = 2, calculating the factorial of n will
require recursion: n * factorial(n - 1).
c. Incorrect. The base case for a recursive function to compute n! (factorial
of n) is n = 0 (not n = 1). If n = 1, calculating the factorial of n will
require recursion: n * factorial(n - 1).
d. Correct. The base case for a recursive function to compute n! (factorial
of n) is n = 0. The factorial of a non-negative integer n, usually written
as “n!”, is the product of all positive integers less than n.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.4 - Describe the relationship between recursion and the divide-
and-conquer strategy of problem-solving.
KEYWORDS: Bloom's: Understand
5. How many recursive calls are made in a recursive algorithm computing the Fibonacci sequence for n = 3?
, a. 3
b. 4
c. 5
d. 6
ANSWER: b
FEEDBACK: a. Incorrect. It requires 4 recursive calls, not 3. For a recursive function
fib, fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base
cases are n = 0 and n = 1, and making two recursive calls to the function
is necessary to compute a single number.
b. Correct. It requires 4 recursive calls. For a recursive function fib, fib(3)
calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base cases are n
= 0 and n = 1, and making two recursive calls to the function is
necessary to compute a single number.
c. Incorrect. It requires 4 recursive calls, not 5. For a recursive function
fib, fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base
cases are n = 0 and n = 1, and making two recursive calls to the function
is necessary to compute a single number.
d. Incorrect. It requires 4 recursive calls, not 6. For a recursive function
fib, fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0). The base
cases are n = 0 and n = 1, and making two recursive calls to the function
is necessary to compute a single number.
POINTS: 1
DIFFICULTY: Introductory
REFERENCES: Introduction to Recursion
QUESTION TYPE: Multiple Choice
HAS VARIABLES: False
LEARNING OBJECTIVES: IADS.CENG.24.1.1.5 - Describe the use of tail recursion in recursive functions and
procedures.
KEYWORDS: Bloom's: Remember
6. Which term describes a recursive algorithm that reaches an end state in a finite time and returns the same
value every time it is used?
a. tail recursion
b. infinite recursion
c. well-defined recursion
d. stack overflow recursion
ANSWER: c
