Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
Solution and Answer Guide
CENGAGE, INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES, 1e, 2024,
9780357673560; CHAPTER 1: RECURSION
TABLE OF CONTENTS
Review Questions ................................................................................................................1
Programming Problems ...................................................................................................... 4
Projects ............................................................................................................................... 6
REVIEW QUESTIONS
1. It is possible to define a recursive function without a base case.
a. true
b. false
Answer: b
Feedback: A recursive function must finish in a finite time, or number of calls. Thus it
must reach a base case where it stops making recursive calls to itself, directly or
indirectly.
2. Which of the following are parts of a recursive function definition?
a. null cases
b. base cases
c. automatic calling
d. composition
Answer: b
Feedback: A recursive function must call on itself; that part is called the recursive
part. And it also must have a part where it stops calling on itself and gives a direct
answer, which are the base cases.
3. When your program has a stack overflow error, it is because the program entered an
infinite recursion.
a. true
b. false
Answer: b
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 1
accessible website, in whole or in part.
, Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
Feedback: The stack overflow error occurs when the space of memory called a stack
is full. This might happen for reasons other than just infinite recursion. Although, when
entering an infinite recursion, this will cause the stack to run out of space.
4. Lucas numbers Ln are defined as follows for a non-negative integer 𝑛𝑛:
𝐿𝐿0 = 2, 𝐿𝐿1 = 1.
For 𝑛𝑛 > 1, 𝐿𝐿𝑛𝑛 = 𝐿𝐿𝑛𝑛−1 + 𝐿𝐿𝑛𝑛−2
What are the values of 𝐿𝐿2 , 𝐿𝐿3 , and 𝐿𝐿4 ?
Answer: 𝐿𝐿2 = 3, 𝐿𝐿3 = 4, 𝐿𝐿4 = 7
Feedback:
𝐿𝐿2 = 𝐿𝐿1 + 𝐿𝐿0 = 1 + 2 = 3.
𝐿𝐿3 = 𝐿𝐿2 + 𝐿𝐿1 = 3 + 1 = 4.
𝐿𝐿4 = 𝐿𝐿3 + 𝐿𝐿2 = 4 + 3 = 7.
5. Which of the following is true about the Lucas numbers definition given in Question 4?
a. The function enters into an infinite recursion.
b. It has two base cases.
c. It has too many base cases.
d. The recursion is ill defined since it depends on two values of Lucas numbers and
not one.
Answer: b
Feedback:
a. Incorrect. The function doesn’t enter into an infinite recursion since for every
value of n it reaches one of the two base cases.
b. Correct. The Lucas number 𝐿𝐿𝑛𝑛 depends on 𝐿𝐿𝑛𝑛−1 and 𝐿𝐿𝑛𝑛−2 , which are smaller
cases than 𝑛𝑛 by one and two, respectively. This means that at each recursive
call the parameter 𝑛𝑛 is reduced. Since 𝑛𝑛 is a non-negative integer, the recursive
calls will eventually reach 𝑛𝑛 = 1 or 𝑛𝑛 = 0. n = 1 and n = 0 are the two base
cases in the recursive definition.
6. Programmer A is assigned to write a procedure that displays numbers by subtracting 3
starting from n until it reaches a negative number. For 𝑛𝑛 = 14, the output should
appear as follows:
14 11 8 5 2 – 1
The proposed pseudocode solution by programmer A is the following:
count(n)
if n < 0
display n
finish the program
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 2
accessible website, in whole or in part.
, Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
else
display n
count(n-3)
Which is true about the solution of programmer A?
a. The recursion is ill-defined because it doesn't have a base case.
b. It doesn’t use recursion.
c. The recursion is ill-defined since it never reaches a base case.
d. It uses tail recursion.
Answer: d
Feedback: Notice that the function has the base case when 𝑛𝑛 is negative. Since when
the function calls itself it does it with parameter n − 3, you know it will reach a
negative number, the base case. Thus, the recursion is well defined. Since the last part
of the procedure or the returning value is a call to the same function, this function
uses tail recursion.
7. The number of combinations of 𝑛𝑛 elements into 𝑘𝑘 elements, 𝐶𝐶𝑘𝑘𝑛𝑛 , is the number of
subsets with 𝑘𝑘 elements that can be formed from a set with 𝑛𝑛 elements, where 𝑛𝑛 and
𝑘𝑘 are non-negative numbers such that 𝑛𝑛 ≥ 𝑘𝑘. 𝐶𝐶𝑘𝑘𝑛𝑛 is also known as the number of ways
of choosing 𝑘𝑘 elements from 𝑛𝑛 indistinguishable elements. A recursive definition of it
can be made as follows:
(Base case 1) 𝐶𝐶𝑛𝑛𝑛𝑛 = 1 for any 𝑛𝑛 ≥ 0.
(Base case 2) 𝐶𝐶0𝑛𝑛 = 1 for any 𝑛𝑛 ≥ 0.
(Recursion) 𝐶𝐶𝑘𝑘𝑛𝑛 = 𝐶𝐶𝑘𝑘−1
𝑛𝑛−1
+ 𝐶𝐶𝑘𝑘𝑛𝑛−1 for 0 < 𝑘𝑘 < 𝑛𝑛.
Compute 𝐶𝐶00 , 𝐶𝐶01 , 𝐶𝐶11 , 𝐶𝐶02 , 𝐶𝐶12 , 𝐶𝐶22 using the recursive definition.
Answer: 𝐶𝐶00 = 1, 𝐶𝐶01 = 1, 𝐶𝐶11 = 1, 𝐶𝐶02 = 1, 𝐶𝐶12 = 2, 𝐶𝐶22 = 1
Feedback: 𝐶𝐶00 = 1 since it is one of the base cases A or B. 𝐶𝐶01 = 1 since it is a base case
B. 𝐶𝐶11 = 1 since it is a base case A. 𝐶𝐶02 = 1 since it is a base case B. 𝐶𝐶12 = 𝐶𝐶1−1
2−1
+ 𝐶𝐶12−1 =
𝐶𝐶01 + 𝐶𝐶11 = 1 + 1 = 2 by the recursion in C. 𝐶𝐶22 = 1 since it is a base case A.
8. What prevents backtracking from testing all possible cases when building a solution?
a. bounding condition
b. infinite recursion
c. base case
d. backtracking stop condition
Answer: a
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 3
accessible website, in whole or in part.
, Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
Feedback:
a. Correct. Backtracking can, if necessary, test all possible solutions, like all the
subsets in the subset sum problem. But using the bounding condition can skip
several options that are no longer feasible solutions to the problem.
b. This is a state that a recursive function can enter if the base case is not
defined correctly.
c. This is where a recursive function ends calling itself recursively.
d. There is no such term when talking of backtracking solutions.
9. When searching for the solution to a problem that might require recursion, what might
be a good strategy to start?
Answer: Work out the smallest possible case.
Feedback: Working with small cases will give you insight on how the general solution
can be formulated. The smallest possible case can be a part of the base case. This
case is usually easy and, in an interview, this can show that you have the right mindset
for problem solving.
10. When using backtracking to find a subset with sum 10 from 𝑋𝑋 = {2,3,4,5,8}, what would
be the next step in the algorithm after reaching 𝑆𝑆 = {2,3,4,5}?
Answer: It stops searching this path since the sum of the elements of 𝑆𝑆 is greater than
10.
Feedback: At each step the algorithm studies two possible options, add a new element
to the set or not. The bounding condition is that the sum of the elements so far is not
greater than the desired number. In the case of 𝑆𝑆 = {2,3,4,5}, the sum of the elements
is 14, so it is impossible to derive a solution from this set by adding new elements.
PROGRAMMING PROBLEMS
1. Write a program that uses recursion to display all the odd positive integers, in
descending order, from n to 1. (LO 1.2.)
For 𝑛𝑛 = 12, the program must display: 11, 9, 7, 6, 5, 3, 1
For 𝑛𝑛 = 7, the program must display: 7, 5, 3, 1
Solution:
odds(n)
if n = 1
display n
else
if n mod 2 = 1
display(n)
odds(n-2)
else
odds(n-1)
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 4
accessible website, in whole or in part.
Chapter 1: Recursion
Solution and Answer Guide
CENGAGE, INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES, 1e, 2024,
9780357673560; CHAPTER 1: RECURSION
TABLE OF CONTENTS
Review Questions ................................................................................................................1
Programming Problems ...................................................................................................... 4
Projects ............................................................................................................................... 6
REVIEW QUESTIONS
1. It is possible to define a recursive function without a base case.
a. true
b. false
Answer: b
Feedback: A recursive function must finish in a finite time, or number of calls. Thus it
must reach a base case where it stops making recursive calls to itself, directly or
indirectly.
2. Which of the following are parts of a recursive function definition?
a. null cases
b. base cases
c. automatic calling
d. composition
Answer: b
Feedback: A recursive function must call on itself; that part is called the recursive
part. And it also must have a part where it stops calling on itself and gives a direct
answer, which are the base cases.
3. When your program has a stack overflow error, it is because the program entered an
infinite recursion.
a. true
b. false
Answer: b
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 1
accessible website, in whole or in part.
, Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
Feedback: The stack overflow error occurs when the space of memory called a stack
is full. This might happen for reasons other than just infinite recursion. Although, when
entering an infinite recursion, this will cause the stack to run out of space.
4. Lucas numbers Ln are defined as follows for a non-negative integer 𝑛𝑛:
𝐿𝐿0 = 2, 𝐿𝐿1 = 1.
For 𝑛𝑛 > 1, 𝐿𝐿𝑛𝑛 = 𝐿𝐿𝑛𝑛−1 + 𝐿𝐿𝑛𝑛−2
What are the values of 𝐿𝐿2 , 𝐿𝐿3 , and 𝐿𝐿4 ?
Answer: 𝐿𝐿2 = 3, 𝐿𝐿3 = 4, 𝐿𝐿4 = 7
Feedback:
𝐿𝐿2 = 𝐿𝐿1 + 𝐿𝐿0 = 1 + 2 = 3.
𝐿𝐿3 = 𝐿𝐿2 + 𝐿𝐿1 = 3 + 1 = 4.
𝐿𝐿4 = 𝐿𝐿3 + 𝐿𝐿2 = 4 + 3 = 7.
5. Which of the following is true about the Lucas numbers definition given in Question 4?
a. The function enters into an infinite recursion.
b. It has two base cases.
c. It has too many base cases.
d. The recursion is ill defined since it depends on two values of Lucas numbers and
not one.
Answer: b
Feedback:
a. Incorrect. The function doesn’t enter into an infinite recursion since for every
value of n it reaches one of the two base cases.
b. Correct. The Lucas number 𝐿𝐿𝑛𝑛 depends on 𝐿𝐿𝑛𝑛−1 and 𝐿𝐿𝑛𝑛−2 , which are smaller
cases than 𝑛𝑛 by one and two, respectively. This means that at each recursive
call the parameter 𝑛𝑛 is reduced. Since 𝑛𝑛 is a non-negative integer, the recursive
calls will eventually reach 𝑛𝑛 = 1 or 𝑛𝑛 = 0. n = 1 and n = 0 are the two base
cases in the recursive definition.
6. Programmer A is assigned to write a procedure that displays numbers by subtracting 3
starting from n until it reaches a negative number. For 𝑛𝑛 = 14, the output should
appear as follows:
14 11 8 5 2 – 1
The proposed pseudocode solution by programmer A is the following:
count(n)
if n < 0
display n
finish the program
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 2
accessible website, in whole or in part.
, Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
else
display n
count(n-3)
Which is true about the solution of programmer A?
a. The recursion is ill-defined because it doesn't have a base case.
b. It doesn’t use recursion.
c. The recursion is ill-defined since it never reaches a base case.
d. It uses tail recursion.
Answer: d
Feedback: Notice that the function has the base case when 𝑛𝑛 is negative. Since when
the function calls itself it does it with parameter n − 3, you know it will reach a
negative number, the base case. Thus, the recursion is well defined. Since the last part
of the procedure or the returning value is a call to the same function, this function
uses tail recursion.
7. The number of combinations of 𝑛𝑛 elements into 𝑘𝑘 elements, 𝐶𝐶𝑘𝑘𝑛𝑛 , is the number of
subsets with 𝑘𝑘 elements that can be formed from a set with 𝑛𝑛 elements, where 𝑛𝑛 and
𝑘𝑘 are non-negative numbers such that 𝑛𝑛 ≥ 𝑘𝑘. 𝐶𝐶𝑘𝑘𝑛𝑛 is also known as the number of ways
of choosing 𝑘𝑘 elements from 𝑛𝑛 indistinguishable elements. A recursive definition of it
can be made as follows:
(Base case 1) 𝐶𝐶𝑛𝑛𝑛𝑛 = 1 for any 𝑛𝑛 ≥ 0.
(Base case 2) 𝐶𝐶0𝑛𝑛 = 1 for any 𝑛𝑛 ≥ 0.
(Recursion) 𝐶𝐶𝑘𝑘𝑛𝑛 = 𝐶𝐶𝑘𝑘−1
𝑛𝑛−1
+ 𝐶𝐶𝑘𝑘𝑛𝑛−1 for 0 < 𝑘𝑘 < 𝑛𝑛.
Compute 𝐶𝐶00 , 𝐶𝐶01 , 𝐶𝐶11 , 𝐶𝐶02 , 𝐶𝐶12 , 𝐶𝐶22 using the recursive definition.
Answer: 𝐶𝐶00 = 1, 𝐶𝐶01 = 1, 𝐶𝐶11 = 1, 𝐶𝐶02 = 1, 𝐶𝐶12 = 2, 𝐶𝐶22 = 1
Feedback: 𝐶𝐶00 = 1 since it is one of the base cases A or B. 𝐶𝐶01 = 1 since it is a base case
B. 𝐶𝐶11 = 1 since it is a base case A. 𝐶𝐶02 = 1 since it is a base case B. 𝐶𝐶12 = 𝐶𝐶1−1
2−1
+ 𝐶𝐶12−1 =
𝐶𝐶01 + 𝐶𝐶11 = 1 + 1 = 2 by the recursion in C. 𝐶𝐶22 = 1 since it is a base case A.
8. What prevents backtracking from testing all possible cases when building a solution?
a. bounding condition
b. infinite recursion
c. base case
d. backtracking stop condition
Answer: a
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 3
accessible website, in whole or in part.
, Solution and Answer Guide: Cengage, Introduction to Algorithms and Data Structures, 1e, 2024, 9780357673560;
Chapter 1: Recursion
Feedback:
a. Correct. Backtracking can, if necessary, test all possible solutions, like all the
subsets in the subset sum problem. But using the bounding condition can skip
several options that are no longer feasible solutions to the problem.
b. This is a state that a recursive function can enter if the base case is not
defined correctly.
c. This is where a recursive function ends calling itself recursively.
d. There is no such term when talking of backtracking solutions.
9. When searching for the solution to a problem that might require recursion, what might
be a good strategy to start?
Answer: Work out the smallest possible case.
Feedback: Working with small cases will give you insight on how the general solution
can be formulated. The smallest possible case can be a part of the base case. This
case is usually easy and, in an interview, this can show that you have the right mindset
for problem solving.
10. When using backtracking to find a subset with sum 10 from 𝑋𝑋 = {2,3,4,5,8}, what would
be the next step in the algorithm after reaching 𝑆𝑆 = {2,3,4,5}?
Answer: It stops searching this path since the sum of the elements of 𝑆𝑆 is greater than
10.
Feedback: At each step the algorithm studies two possible options, add a new element
to the set or not. The bounding condition is that the sum of the elements so far is not
greater than the desired number. In the case of 𝑆𝑆 = {2,3,4,5}, the sum of the elements
is 14, so it is impossible to derive a solution from this set by adding new elements.
PROGRAMMING PROBLEMS
1. Write a program that uses recursion to display all the odd positive integers, in
descending order, from n to 1. (LO 1.2.)
For 𝑛𝑛 = 12, the program must display: 11, 9, 7, 6, 5, 3, 1
For 𝑛𝑛 = 7, the program must display: 7, 5, 3, 1
Solution:
odds(n)
if n = 1
display n
else
if n mod 2 = 1
display(n)
odds(n-2)
else
odds(n-1)
© 2024 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly 4
accessible website, in whole or in part.
