##
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.