Can you give me another simple example of recursion?

Sure. Let's consider finding the sum of an arithmetic progression.

What's an arithmetic progression?

It's a sequence of numbers in which each term after the first differs from its predecessor by the same amount. For instance, the sequence 3, 10, 17, 24, 31 is an arithmetic progression, because each term after the first is seven greater than its predecessor. The sum of this progression is 3 + 10 + 17 + 24 + 31, or 85.

I seem to recall that there's a formula for that.

Yes, there is, but you'll have to ignore it for the moment if you want an example of recursion. The point of recursion is to let the program determine the amount of computation that needs to be done -- you don't need it if you have a canned formula that uses a fixed amount of computation.

Okay. But how are we going to use recursion this time? I don't see any mathematical function that could be defined by cases. Besides, this time we don't even know in advance how many operands there will be. Your example progression had five terms to add up, but a different arithmetic progression could have more or fewer, right?

That's right. But in fact we only need to know three things about an arithmetic progression in order to figure out everything about it: what its first term is, what the constant difference between adjacent terms is, and how many terms there are. From those three data we can reconstruct the entire progression.

So?

So we can use those three pieces of information as the operands of our sum-of-progression procedure. When we need the particular terms of the progression, we can generate them one at a time just by adding the difference over and over again.

Now we're ready to see how recursion comes in. Since the number of terms is an operand -- call it n -- we can divide the cases according to the value of n. If n is zero, so that there are no terms at all in the progression, the sum of the terms is zero. On the other hand, if n is greater than zero, then we can find the sum of the progression by adding its first term to the sum of a progression consisting of the rest of the terms.

What? How would that work in the example progression?

Well, in that case n is 5, which is greater than zero. So the sum of the progression 3, 10, 17, 24, 31 is 3 + (the sum of the progression 10, 17, 24, 31). That's a progression of length 4, and 4 is greater than zero. So the sum of the progression 10, 17, 24, 31 is 10 + (the sum of the progression 17, 24, 31). And so on:

sum of 3, 10, 17, 24, 31 = 3 + (sum of 10, 17, 24, 31)
                         = 3 + (10 + (sum of 17, 24, 31))
                         = 3 + (10 + (17 + (sum of 24, 31)))
                         = 3 + (10 + (17 + (24 + (sum of 31))))
                         = 3 + (10 + (17 + (24 + (31 + sum of nothing))))
                         = 3 + (10 + (17 + (24 + (31 + 0))))
                         = 3 + (10 + (17 + (24 + 31)))
                         = 3 + (10 + (17 + 55))
                         = 3 + (10 + 72)
                         = 3 + 82
                         = 85

It still seems circular.

No, it's recursive. It's not circular, because we're descending the helical staircase towards a stopping point. Each time we have to figure the sum of a progression, the progression gets smaller. This can't go on forever, and as soon as we reach bottom we can work out the result.

And this works in Scheme, too?

Here it is:

(define (sum-of-progression first-term difference n)
  (if (zero? n)
      0
      (+ first-term
         (sum-of-progression (+ first-term difference)
                             difference
                             (sub1 n)))))

Because the new progression, the one from which the first term has been removed, has a different first term. The new progression's first term is the old first term plus the difference between adjacent terms. And the third operand is one less in the recursive call, because the new progression is one term shorter than the old one.

You remember, I said we'd generate the terms of the sequence as we needed them. That addition is the one that generates each term as it is needed. The outer addition is the one that adds up the terms after we've formed them all.

Now, let's use that procedure to find the sum of all the integers from 1 to 1000, and then of all the odd integers from 1 to 199:

> (sum-of-progression 1 1 1000)
500500
> (sum-of-progression 1 2 100)
10000

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/sum-of-progression.html

Copyright 1995 by John David Stone (stone@math.grin.edu)