Instructor's Manual for

M.B. Feldman and E.B. Koffman, Ada 95 Problem Solving and Program Design, 3rd edition. Copyright 1999, Addison-Wesley Publishing Company. All Rights Reserved.

Questions and comments to mfeldman@seas.gwu.edu.

---

Chapter 14 Recursion

last revised March 1999

Chapter Objectives

The student will

1. be introduced to the concept of a recursive algorithm,
2. compare recursive and iterative implementations of several algorithms,
3. learn to write simple recursive procedures and functions,
4. learn to manipulate one-dimensional arrays recursively,
5. study more complicated recursive procedures for Towers-of-Hanoi and region filling, and
6. study recursive binary searching.

New Terms

Section 14.1

recursive procedure	recursive function
stopping case

Section 14.2

activation frame

parameter stack

Section 14.3

Fibonacci Sequence

greatest common divisor (GCD)

Section 14.4

palindrome

Section 14.5

Towers-of-Hanoi problem

blob

Section 14.6

binary search

Notes and Suggestions

General Suggestions

Recursion is extremely important in computer science; its use pervades all areas of the field, and students should be introduced to it as early as possible. Many students will not feel comfortable with recursion for a while, perhaps not until later in their education. Students with experience in BASIC or Fortran may find recursion somewhat mysterious, because those languages do not allow it. Give your students a lot of practice problems.

Section 14.1

Recursion is best learned by understanding and tracing a number of examples. The function Multiply is a good starting point.

Section 14.2

Tracing a recursive program is the best way to understand it. Some teachers actually use slips of paper, tacked one at a time to the board, to illustrate the LIFO recursive activations. Instead of the routine "calling itself," which seems illogical, each activation creates a "clone" of itself to handle a smaller part of the data.

Section 14.3

Mathematical functions lend themselves easily to recursive implementations. These are easy to understand but difficult to justify, because students will notice the iterative solution right away.

Section 14.4

You may have to work hard to "sell" recursive array manipulations, because the iterative solutions are so natural. It is important that students try to understand the recursive solutions, because they are preparation for algorithms like Quicksort that they will see in later courses.

Section 14.5

Towers of Hanoi is a bit difficult to understand, but appealing to the students' sense of logic without worrying about implementation details will prove fruitful. This is a good example of the power of recursion; it is very difficult to come up with a nonrecursive solution. Once students understand the solution to this problem, they realize how innocent it looks but how quickly the number of moves explodes. The self-check exercises provide food for thought.

The blob case study will probably appeal to students with a penchant for graphics. Its elegance is difficult to match with an iterative algorithm.

Section 14.6

Binary search is one of the most fundamental algorithms in computing. Its recursive version is more natural than its iterative one.