Recursion requires you to completely change how you approach a problem. Let's say we want the list of prime numbers from 2 to 20. We can start with producing the list of all numbers between 2 and 20:
(define (numbers from to)
(if (> from to)
empty
(cons from (numbers (+ from 1) to))))
(numbers 2 20) ; => '(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
numbers is a recursive function definition which implements the simple observation that the list of numbers from 2 to 20 is the same as 2 followed by the list of numbers from 3 to 20, and so on. We also have a terminating condition: the list of numbers from 21 to 20 is the empty list.
You'll notice that every prime number from 2 to 20 is in that list, so, in a sense, we're done -- the original requirements did not say that the list must contain only the prime numbers.
The actual problem is that the list contains too many elements, and we need to remove some of them. For example, 2 is a prime number, but every multiple of 2 is not and can be removed, the same can be done for 3 and so on. In general we can write another recursive function to drop every multiple of a number from a list:
(define (drop start step l)
(if (null? l)
empty
(let ([head (first l)]
[tail (rest l)])
(cond ((< head start)
(cons head (drop start step tail)))
((< start head)
(drop (+ start step) step l))
((= start head)
(drop (+ start step) step tail))))))
(drop 4 2 (numbers 2 20)) ; => '(2 3 5 7 9 11 13 15 17 19)
If we drop every multiple of the first number we see in a list, and do that recursively only the prime numbers will remain:
(define (primes l)
(if (null? l)
empty
(let ([head (first l)]
[tail (rest l)])
(cons head (primes (drop (+ head head) head tail))))))
(primes (numbers 2 20)) ; => '(2 3 5 7 11 13 17 19)
You'll notice that the program above does not actually calculate any prime number, it just removes all non-primes from the list. For more details on this algorithm, you can check out: Sieve of Eratosthenes - Wikipedia
Ok, the next part is going to be more subtle: what if you wanted every prime number that there is? There is an infinite number of them, of course, but this is not an issue if we use recursion.
We can use the exact same strategy, except we'll use streams instead of lists. First, here is numbers changed to produce all the numbers starting from a certain number.
(define (numbers from)
(stream-cons from (numbers (+ from 1))))
(numbers 2) ; => #<stream>
Note that the numbers is still recursive, but there is no longer any terminating condition. The list of numbers from 2 is simply 2 plus the list of numbers from 3 and so on, forever. 'When you try to print it, Racket, prudently, prints out just "#", but you can take some numbers out, here are the first 20 numbers from that list:
(stream->list (stream-take (numbers 2) 20))
'(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21)
We can re-write drop to drop multiples of numbers from infinite streams, producing an infinite stream of numbers. All we need to do is remove the terminating condition for the recursion and use stream-cons instead of cons and stream-first, stream-rest instead of first and rest:
(define (drop start step l)
(let ([head (stream-first l)]
[tail (stream-rest l)])
(cond ((< head start)
(stream-cons head (drop start step tail)))
((< start head)
(drop (+ start step) step l))
((= start head)
(drop (+ start step) step tail)))))
(stream->list (stream-take (drop 4 2 (numbers 2)) 20))
'(2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39)
And we can rewrite primes the same way:
(define (primes l)
(let ([head (stream-first l)]
[tail (stream-rest l)])
(stream-cons head (primes (drop (+ head head) head tail)))))
(stream->list (stream-take (primes (numbers 2)) 20))
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
So, basically, the value returned by (primes (numbers 2)) is the list of all the prime numbers that exist. It is an infinite list, but Racket can handle it just fine. You can take as many primes from that list as you want, but taking all of them will take an infinite amount of time....
Alex.
).
