Principle 12.1.2. EFFECTIVE DESIGN: Efficiency.
Iterative algorithms and methods are generally more efficient than recursive algorithms that do the same thing.
Section 12.1 Introduction
The pattern in Figure 12.1.1 is known as the Sierpinski gasket. Its overall shape is that of an equilateral triangle. But notice how inside the outer triangle there are three smaller triangles that are similar to the overall pattern. And inside each of those are three even smaller triangles, and so on. The Sierpinski gasket is known as a fractal because when you divide it up, you end up with a smaller version of the overall pattern. The overall gasket pattern is repeated over and over, at smaller and smaller scales, throughout the figure.
How would you draw this pattern? If you try to use some kind of nested loop structure, you’ll find that it is very challenging. It can be done using loops, but it isn’t easy. On the other hand, if you use an approach known as recursion, this problem is much easier to solve. It’s a little bit like the representation issue we discussed in Chapter 5. Your ability to solve a problem often depends on how you represent the problem. Recursion gives you another way to approach problems that involve repetition, such as the problem of drawing the Sierpinski gasket.
The main goal of this chapter is to introduce recursion as both a problem-solving technique and as alternative to loops (which we discussed in Chapter 6) for implementing repetition. We begin with the notion of a recursive definition, a concept used widely in mathematics and computer science. We then introduce the idea of a recursive method, which is the way recursion is implemented in a program.
Recursion is a topic that is taken up in considerable detail in upper-level computer science courses, so our goal here is mainly to introduce the concept and give you some idea of its power as a problem-solving approach. To illustrate recursion, we use a number of simple examples throughout the chapter. One risk in using simple examples, though, is that you might be tempted to think that recursion is only good for “toy problems.” Nothing could be further from the truth. Recursion is often used for some of the most difficult algorithms. Some of the exercises at the end of the chapter are examples of more challenging problems.
Subsection 12.1.1 Recursion as Repetition
A recursive method is a method that calls itself. An iterative method is a method that uses a loop to repeat an action. In one sense, recursion is an alternative to the iterative (looping) control structures we studied in Chapter 6. In this sense, recursion is just another way to repeat an action.
For example, consider the following iterative method for saying “Hello” N times:
public void hello(int N) {
for (int k = 0; k < N; k++)
System.out.println("Hello");
} // hello()
A recursive version of this method would be defined as follows:
public void hello(int N) {
if (N > 0) {
System.out.println("Hello");
hello(N - 1); // Recursive call
}
} // hello()
This method is recursive because it calls itself when N is greater than 0. However, note that when it calls itself, it passes \(N-1\) as the value for its parameter. If this method is initially called with N equal to 5, the following is a trace of what happens. The indentations indicate each time the method calls itself:
hello(5)
Print "Hello"
hello(4)
Print "Hello"
hello(3)
Print "Hello"
hello(2)
Print "Hello"
hello(1)
Print "Hello"
hello(0)
Thus, “Hello” will be printed five times, just as it would be in the iterative version of this method.
So, in one sense, recursion is just an alternative to iteration. In fact, there are some programming languages, such as the original versions of LISP and PROLOG, that do not have loop structures. In these languages, all repetition is done by recursion. In contrast, if a language contains loop structures, it can do without recursion. Anything that can be done iteratively can be done recursively, and vice versa.
Moreover, it is much less efficient to call a method five times than to repeat a for loop five times. Method calls take up more memory than loops and involve more computational overhead —for such tasks as passing parameters, allocating storage for the method’s local variables, and returning the method’s results. Therefore, because of its reliance on repeated method calls, recursion is often less efficient than iteration as a way to code a particular algorithm.
Exercises Self-Study Exercises
1. mystery(5)?
- 0 1 2 3 4 5 6
- Yes the recursion would end when
N > 5. - 0 1 2 3 4 5
- What happens when N = 6?
- 1 2 3 4 5 6
- What happens when N = 0?
- None of the above
- Try again.
What would be printed if we call the following method with the expression
mystery(0)?public void mystery(int N) {
System.out.print(N + " ");
if (N <= 5)
mystery(N + 1);
} // mystery()
Hint.
Try to trace the method calls, writing down the output as you go.
2. mystery(100)?
- 0 1 2 3 4 5 6 ... 100
- Look carefully at the
ifcondition. - 100
- Right, no recursive calls would result in this case.
- 100 99 98 ... 0
- Look carefully at the
ifcondition. - None of the above
- Try again.
What would be printed if we call the following method with the expression
mystery(100)?public void mystery(int N) {
System.out.print(N + " ");
if (N <= 5)
mystery(N + 1);
} // mystery()
Hint.
Try to trace the method calls, writing down the output as you go.
3. mystery2(5)?
- 5 4 3 2 1 0
- What makes it stop at 0??
- 5 4 3 2 1
- What makes it stop at 1?
- 5 4 3 2 1 0 -1 -2 -3 ...
- Right, the recursion never stops. It’s infinite.
- None of the above
- Try again.
What would be printed if we call the following method with the expression
mystery2(5)?public void mystery2(int N) {
System.out.print(N + " ");
if (N <= 5)
mystery2(N - 1);
} // mystery()
Hint.
Try to trace the method calls, writing down the output as you go.
Subsection 12.1.2 Recursion as a Problem-Solving Approach
Given that recursion is not really necessary—if a programming language has loops—and is not more efficient than loops, why is it so important? The answer is that, in a broader sense, recursion is an effective approach to problem solving. It is a way of viewing a problem. It is mostly in this sense that we want to study recursion.
Recursion is based on two key problem-solving concepts: divide and conquer and self-similarity. In recursive problem solving we use the divide-and-conquer strategy repeatedly to break a big problem into a sequence of smaller and smaller problems until we arrive at a problem that is practically trivial to solve.
What allows us to create this series of subproblems is that each subproblem is similar to the original problem—that is, each subproblem is just a smaller version of the original problem. Look again at the task of saying “Hello” N times. Solving this task involves solving the similar task of saying “Hello” \(N-1\) times, which can be divided into the similar task of saying “Hello” \(N-2\) times. And so on.
The ability to see a problem as being composed of smaller, self-similar problems is at the heart of the recursive approach. And although you might not have thought about this before, a surprising number of programming problems have this self-similarity characteristic.
Principle 12.1.3. PROGRAMMING TIP: Divide and Conquer.
Many programming problems can be solved by dividing them into smaller, simpler problems. For recursive solutions, finding the key to the subproblem often holds the solution to the original problem.
You have attempted of activities on this page.
