Could a programmer use recursion to write her own predicates, too?
Sure. A predicate is just a procedure that returns a Boolean value. If recursion can help you find that Boolean value, by all means use it.
Can you give me an example?
Well, we could write a procedure that takes an integer and determines whether it's prime. Let's stipulate that the operand has to be greater than 1, so that we can stay out of terminological disputes about whether 1, 0, or negative numbers are prime; this way we can just say that a number is prime if its only exact divisors are itself and 1.
There must be some way of breaking that definition down into cases, since you can use recursion.
That's right. Start by looking at it this way: A number n is prime if it has no divisors in the range from 2 to n - 1; it is not prime if it has even one divisor in that range. We can break the search for a divisor in that range into cases: If 2 divides n, we know right way that n is not prime; otherwise, we search for a divisor in the range from 3 to n - 1. Then if 3 divides n, we're done, and n is not prime; otherwise, we search for a divisor in the range from 4 to n - 1. Eventually, this range shrinks to nothing, since we keep moving up the lower bound; if the lower bound exceeds the upper one, we have excluded all the possible divisors, and n is prime.
We can write a recursive procedure to do the searching. The predicate
has-divisor-in-range? will take a number and the lower and
upper bounds of the range of possible divisors, and determine whether the
number has a divisor in that range:
(define (has-divisor-in-range? n lower-bound upper-bound)
(if (< upper-bound lower-bound)
#f ; range exhausted; no divisor found
(if (divisible? n lower-bound)
#t ; divisor found
(has-divisor-in-range? n (add1 lower-bound) upper-bound))))
And from this we can define the prime? predicate directly:
Here are some sample runs:(define (prime? n) (not (has-divisor-in-range? n 2 (sub1 n))))
I noticed the computer had to think for a second about that last one.> (prime? 7) #t > (prime? 45) #f > (prime? 10007) #t
Yeah, well, from the point of view of getting the answer as quickly as
possible, this definition of prime? is terrible. I showed it to
you because it corresponds closely to the mathematical definition. But
there are some easy ways to improve it by eliminating some of the
divisibility tests.
Think about what the procedure is doing, after all. To find out whether 10007 is prime, it's checking to see whether the division comes out even when you divide by 2, by 3, by 4, by 5, by 6, ..., by 10004, by 10005, and by 10006. Well, the divisions at the end are clearly superfluous; if n is large, it's not going to be evenly divisible by any number close to n. What would the quotient be?
Actually, you could stop a lot earlier. If you don't find a divisor in the first half of the range from 2 to n - 1, it's pointless to check the second half, since the quotient would have to be between 1 and 2, which is impossible.
That's right, and just changing (sub1 n) to (half
n) in the definition of prime? will make the predicate
deliver exactly the same answers almost twice as fast.
An even better idea is to use the square root of n as the upper bound. The thinking here is that if there is an exact divisor d greater than the square root of n, then the quotient n/d is also a divisor of n, and it must be less than the square root of n. So if we don't find such a quotient before reaching the square root of n, it's pointless to search on the other side of the square root.
Why couldn't both d and n/d be greater than the square root of n?
Because then their product would have to be greater than the square of the square root of n -- that is, n would have to be greater than n, which is impossible.
So a better way to write the prime? predicate is
Is this the best approach possible?(define (prime? n) (not (has-divisor-in-range? n 1 (integer-square-root n))))
No. But there is no unique ``best approach''; an algorithm that is appropriate for testing small numbers -- say, those less than 1000000 -- might be hopelessly inadequate for determining whether some hundred-digit number is prime, while the elaborate number-theoretical strategies that can be usefully brought to bear on those giants would involve enormous overhead when applied to small numbers.
One way to improve the code just given by another factor of almost 2 is to test even and odd numbers separately:
; This procedure presupposes that lower-bound is odd.
(define (has-odd-divisor-in-range? n lower-bound upper-bound)
(if (< upper-bound lower-bound)
#f ; range exhausted; no divisor found
(if (divisible? n lower-bound)
#t ; divisor found
(has-odd-divisor-in-range? n (+ lower-bound 2) upper-bound))))
(define (prime? n)
(if (even? n)
(= n 2)
(not (has-odd-divisor-in-range? n 3 (integer-square-root n)))))
Next topic
Previous topic
Table of contents
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/scheme-web/primality.html