Section 4.4 The Three Laws of Recursion
Just as robots in Isaac Asimov’s stories must obey
three laws 1 , all recursive algorithms must obey three important laws:
A recursive algorithm must have a base case.
A recursive algorithm must change its state and move toward the base case.
A recursive algorithm must call itself recursively.
Let’s look at each one of these laws in more detail and see how it was used in the arraySum algorithm. First, a base case is the condition that allows the algorithm to stop recursing. A base case is typically a problem that is small enough to solve directly. In the arraySum algorithm the base case is a list of length 1.
To obey the second law, we must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way. In the
arraySum algorithm our primary data structure is a list, so we must focus our state-changing efforts on the list. Since the base case is a list of length 1, a natural progression toward the base case is to shorten the list. This is exactly what happens on line 9 of
Listing 4.3.2 when we call
arraySum with a shorter list.
The final law is that the algorithm must call itself. This is the very definition of recursion. Recursion is a confusing concept to many beginning programmers. As a novice programmer, you have learned that methods are good because you can take a large problem and break it up into smaller problems. The smaller problems can be solved by writing a method to solve each problem. When we talk about recursion it may seem that we are talking ourselves in circles. We have a problem to solve with a method, but that method solves the problem by calling itself! But the logic is not circular at all; the logic of recursion is an elegant expression of solving a problem by breaking it down into a smaller and easier problems.
In the remainder of this chapter we will look at more examples of recursion. In each case we will focus on designing a solution to a problem by using the three laws of recursion.
Exercises Self Check
1.
How many recursive calls are made when computing the sum of the list [2, 4, 6, 8, 10]?
6
There are only five numbers on the list, the number of recursive calls will not be greater than the size of the list.
5
The initial call to arraySum is not a recursive call.
4
the first recursive call passes the list [4, 6, 8, 10], the second [6, 8, 10] and so on until [10].
3
This would not be enough calls to cover all the numbers on the list
2.
Suppose you are going to write a recursive function to calculate the factorial of a number. fact(n) returns n * n-1 * n-2 * … Where the factorial of zero is defined to be 1. What would be the most appropriate base case?
n == 0
Although this would work there are better and slightly more efficient choices. since fact(1) and fact(0) are the same.
n == 1
A good choice, but what happens if you call fact(0)?
n >= 0
This basecase would be true for all numbers greater than zero so fact of any positive number would be 1.
n <= 1
Good, this is the most efficient, and even keeps your program from crashing if you try to compute the factorial of a negative number.
You have attempted
of
activities on this page.
