Previous Section
 < Free Open Study > 
Next Section

7.6 Using Recursion to Simplify Solutions

So far, we have looked at examples that could just as easily (or more easily) have been written as iterative routines. At the end of the chapter, we talk more about choosing between iterative and recursive solutions. For many problems, however, for which using recursion simplifies the solution.

The first problem we consider is a function, Combinations, that tells us how many combinations of a certain size can be made out of a total group of elements. For instance, if we have 20 different books to pass out to 4 students, we can easily see that-to be equitable-we should give each student 5 books. But how many combinations of 5 books can be made out of a group of 20 books?

A mathematical formula can be used for solving this problem. Given that C is the total number of combinations, group is the total size of the group from which to pick, members is the size of each subgroup, and group >= members,

Click To expand

Because this definition of C is recursive, it is easy to see how a recursive function could be used to solve the problem.

Let's summarize our problem.

The resulting recursive function, Combinations, is listed here.

int Combinations(int group, int members)
// Pre:  group and members are positive.
// Post: Function value = number of combinations of members size
//       that can be constructed from the total group size.
  if (members == 1)
    return group;             // Base case 1
  else if (members == group)
    return 1;                 // Base case 2
    return (Combinations(group-1, members-1) +
            Combinations(group-1, members));

Figure 7.2 shows the processing of this function to calculate the number of combinations of 3 elements that can be made from a set of 4.

Click To expand
Figure 7.2: Calculating Combinations (4. 3)

Returning to our original problem, we can now find out how many combinations of 5 books can be made from the original set of 20 books with the statement

std::cout  << "Number of combinations = "  << Combinations(20, 5)
           << std::end1;

Writing a recursive solution to a problem that is characterized by a recursive definition, like Combinations or Factorial, is fairly straightforward.

Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)