In all of these examples, we know exactly what to do in order to compute the result of a procedure. But what if the amount of computation depends on the operand? For instance, suppose you want to write a general factorial procedure -- given a positive integer n, compute the product n! of all the integers up to n. The number of multiplications you need depends on what n is.

That's true, but there's a way in Scheme to let the operand control the amount of computation that is done -- several ways, in fact. Think about how a mathematician would define the factorial ``by cases.''

With an if-expression, you mean?

Sure. There's a pattern in the factorials: 1! = 1, 2! = 1 x 2 = 2, 3! = 1 x 2 x 3 = 6, 4! = 1 x 2 x 3 x 4 = 24, 5! = 1 x 2 x 3 x 4 x 5 = 120, 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720, and so on. You see how each factorial is related to the one that comes before it?

Yes, you're multiplying one more number into the product each time. That's exactly what I mean -- the number of multiplications depend on what n is.

Well, the mathematician would capture this pattern by considering just two cases. If n is 1, n! is 1; and if n is greater than 1, n! is (n - 1)! x n. (Actually, a mathematician would probably start with 0! = 1 and compute 1! as 0! x 1 = 1 x 1 = 1. But it's the same principle.)

That's no good. It's circular -- you're using factorials to define factorials. You're using that factorial symbol to define itself.

Not exactly. I'm using smaller factorials to define larger ones, but that's not circular so long as I don't also use larger ones to define smaller ones. It's more like a helix than a circle: I can climb down the spiral staircase without ever returning to my starting point, because I'm always making downwwards progress and because there's a natural stopping point at 0 or 1.

What do you mean, a natural stopping point?

If I want to find out what 6! is, I can find out by working my way down until I reach 0!, then multiplying my way out again:

6! = 5! x 6
6! = (4! x 5) x 6
6! = ((3! x 4) x 5) x 6
6! = (((2! x 3) x 4) x 5) x 6
6! = ((((1! x 2) x 3) x 4) x 5) x 6
6! = (((((0! x 1) x 2) x 3) x 4) x 5) x 6
6! = (((((1 x 1) x 2) x 3) x 4) x 5) x 6
6! = ((((1 x 2) x 3) x 4) x 5) x 6
6! = (((2 x 3) x 4) x 5) x 6
6! = ((6 x 4) x 5) x 6
6! = (24 x 5) x 6
6! = 120 x 6
6! = 720

Not exactly. But you still have to do all the multiplications.

Yes, but that's exactly what we're looking for -- a way to describe a variable amount of computation in a fixed definition, so that we can let the amount of computation be determined by the operand.

What do you mean? This wouldn't work in a Scheme procedure, would it?

Sure. Just as mathematicians define functions ``by cases,'' Scheme can define procedures with if-expressions:

(define (factorial n)
  (if (zero? n)
      1
      (* (factorial (sub1 n)) n)))

It won't work, though. You can't use the variable factorial in its own definition.

You can use a variable anywhere, provided that it is defined before you to evaluate it. The variable factorial won't be evaluated until the procedure is actually called -- it's not evaluated during the definition process, because no factorials are being computed at that point.

So that circular definition is legal in Scheme?

It's not a circular definition. The technical name for it is ``recursive.'' Yes, it is legal -- it's a perfectly good way of defining the factorial function for non-negative integer operands. Try it if you don't believe me:

> (factorial 0)
1
> (factorial 1)
1
> (factorial 5)
120
> (factorial 20)
2432902008176640000

The same way it did when I descended the spiral staircase earlier: Scheme works its way down through smaller and smaller operands until it reaches 0!, then performs all of the multiplications that have piled up to obtain the final result.

So to figure (factorial 20), it had to figure (factorial 19), and to figure that, it had to figure (factorial 18), and so on back?

That's right. The whole process involved twenty-one calls to the procedure, even though the programmer only types one of them.

Where do the others come from?

One procedure call often generates others automatically. When you call, say, the is-multiple? procedure, that procedure calls the zero? procedure a couple of times and perhaps also the remainder procedure once. There can be any number of layers of indirection: Procedure A can call procedure B, which calls procedure C, which calls procedure D, and so on. (Of course, eventually you must reach a procedure which doen't make any further calls; otherwise you'd never get a result back.) Recursion is just the special case in which A and B and C and D all happen to be the same procedure.

But if the procedure keeps calling itself, how does it ever get stopped? How does it know when to stop?

In the case of the factorial procedure, the operand gets smaller on each new call. Eventually it gets down to zero. Then the recursion can stop. When the operand is zero, the test in the if-expression comes out true, so the consequent is evaluated and the alternate is not. There's no procedure call in the consequent -- it's just the constant 1 -- so the recursion does stop there.

What would happen if we didn't provide a stopping point?

You're suggesting that we write something like this:

(define (no-stopping-point n)
  (add1 (no-stopping-point (sub1 n))))

Yes. What happens then?

About what you'd expect. Scheme accepts the definition, but when you call the procedure, you never get an answer back: it keeps calling itself forever -- or, more realistically, until you interrupt it or something breaks. On my computer, I eventually got the following error message:

Pid 2238 was killed due to stack growth failure.
Possible causes: insufficient memory or swap space,
or stack size exceeded maxssiz.
Segmentation fault (core dumped)

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/recursion.html

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