C++ Programming: From Problem Analysis to Program Design, Eighth Edition 15-1
Chapter 15
Recursion
A Guide to this Instructor’s Manual:
We have designed this Instructor’s Manual to supplement and enhance your teaching
experience through classroom activities and a cohesive chapter summary.
This document is organized chronologically, using the same headings that you see in the
textbook. Under the headings, you will find lecture notes that summarize the section, Teacher
Tips, Classroom Activities, and Lab Activities. Pay special attention to teaching tips and
activities geared towards quizzing your students and enhancing their critical thinking skills.
In addition to this Instructor’s Manual, our Instructor’s Resources also contain PowerPoint
Presentations, Test Banks, and other supplements to aid in your teaching experience.
At a Glance
Instructor’s Manual Table of Contents
• Overview
• Objectives
• Teaching Tips
• Quick Quizzes
• Class Discussion Topics
• Additional Projects
• Additional Resources
• Key Terms
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 15-2
Lecture Notes
Overview
The problems in previous chapters have been solved using an iterative technique.
Chapter 15 introduces another technique for problem solving called recursion. In some
cases, recursion provides a less complicated solution than iteration. Students will learn
about the base case and general case of a recursive definition and explore how to
implement recursive functions.
Objectives
In this chapter, the student will:
• Learn about recursive definitions
• Explore the base case and the general case of a recursive definition
• Discover what a recursive algorithm is
• Learn about recursive functions
• Become familiar with direct and indirect recursion
• Explore how to use recursive functions to implement recursive algorithms
• Become aware of recursion vs. iteration
Teaching Tips
Recursive Definitions
1. Define recursion as a process of solving a problem by reducing it to smaller versions of
itself.
Teaching
Tip
Recursion is a conceptually difficult topic. Ask your students if they have had
experience with recursive techniques in other classes. If there are students who
are new to this topic, plan to spend some additional time working through
examples in class. Encourage students to speak up if they have any questions.
2. Examine the factorial problem in this section and discuss the recursive solution.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 15-3
Teaching
Tip
You might want to compare the recursive solution of a factorial in this section
with an iterative version to help students understand the concept of recursion.
Here is one iterative solution: (see: FAQ > An introduction to recursion)
http://faq.cprogramming.com/cgi-
bin/smartfaq.cgi?id=1073086407&answer=1074726763
3. Use Figure 15-1 to illustrate the process of recursion in the factorial function.
Teaching
Tip
Recall the stack unwinding section that discussed the propagation of exceptions
in Chapter 14. Compare this process to recursive function calls. Emphasize that
computers typically use stacks to process recursive functions.
Direct and Indirect Recursion
1. Discuss the difference between direct and indirect recursion.
2. Explain what tail recursion is, and revisit the factorial function to demonstrate tail
recursion.
Infinite Recursion
1. Describe how infinite recursion occurs.
2. Explain how infinite recursion impacts computer memory. Use your previous
discussion on stacks to clarify.
3. Discuss the steps involved in designing a recursive definition.
Teaching
Tip
Emphasize the importance of establishing an appropriate base case in a recursive
function to prevent infinite recursion.
Quick Quiz 1
1. Define recursion.
2. In recursion, the case for which a solution is obtained directly is called the
____________________ case.
3. True or False: In a recursive algorithm, a general case must eventually be reduced to a
base case.
4. A(n) ____________________ function is a function in which the last step executed is
Problem Solving Using Recursion
1. Discuss Example 15-1, which is the problem of finding the largest element of an array.
Using Figure 15-2, first review the iterative solution. Then step through the pseudocode
for the recursive version. Use Figure 15-4 to illustrate how the recursive version works.
Finally, step through the code for the recursive version.
Teaching
Tip
Discuss this example in detail and make sure students do not get left behind.
2. Discuss Example 15-2, which is the classic Fibonacci number problem. Review the
iterative version, and then compare it to the recursive version.
Teaching
Tip
Make sure to step though the recursive Fibonacci function with the sample input
provided in this section. Using the actual input with the diagram in Figure 15-5
will clarify the recursive process for your students.
3. Describe the Tower of Hanoi problem using Figures 15-6 and 15-7. Step through the
recursive solution.
Teaching
Tip
Ask your students to become familiar with this problem before class because the
problem statement itself is somewhat complicated. The class discussion can then
primarily focus on the implementation of the problem solution.
Tower of Hanoi: Analysis
1. Discuss how long it would take to complete a Tower of Hanoi solution, both in a real-
life scenario and with a computer-generated simulation.
Recursion or Iteration?
© 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
1. Discuss the differences between iterative and recursive solutions to problems. In
particular, note the differences in the use of control structures.
2. Describe the two issues involved in deciding whether to use iteration or recursion to
solve a problem: the nature of the problem and efficiency.
Teaching
Tip
Note that efficiency is not as much a consideration in the choice between
iteration or recursion with the speed and memory of contemporary computers.
The choice to use recursion should reflect on the simplicity of the resulting
algorithm.
Quick Quiz 2
1. In the Fibonacci sequence, the third Fibonacci number is the ____________________
of the first two numbers.
2. ____________________ control structures use a looping structure.
3. A(n) ____________________ control structure is used to control the repeated calls in
recursion.
4. True or False: An iterative function executes more slowly than its recursive counterpart.
Class Discussion Topics
1. Note that indirect recursion is also referred to as mutual recursion. Although this
chapter does not provide examples of indirect recursion for the sake of simplicity, you
might illustrate the concept with a simple example. Why is indirect recursion in C++
discouraged?
2. In this chapter, mission control applications were discussed as a case in which iteration
might be preferable to recursion. Ask students to think of more applications in which
iteration might be preferable and why.
Additional Projects
1. Write a recursive function that takes a nonnegative integer as an argument and prints
each digit of that integer out (in order from left or right) on a separate line. The base
2. Write two functions that call each other to determine whether a nonnegative number n is
odd or even. (Note that the normal approach is simply to calculate n % 2; however, this
1) recursively. Test your functions in a program.
Additional Resources
1. Recursive Primer Using C++:
2. Absolute Recursive Factorial Function C++:
3. Tutorial on Recursion:
4. Tail Recursion:
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 15-7
➢ Recursive definition: a definition in which something is defined in terms of a smaller
version of itself
➢ Recursive function: a function that calls itself, either directly or indirectly
➢ Rightmost bit (of x): the remainder of x after division by 2
➢ Tail recursive function: a recursive function in which the last statement executed is the
recursive call