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 6Nothing circular about that, is there?
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:
``If n is zero, n! is 1; otherwise, n! is the product of (n - 1)! and n.'' Sounds perfect.(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
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:
Wow. How does it work?> (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,
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
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:
so that every time we call the procedure we'd call it again?(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:
The moral: Recursion requires a stopping point.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)
Table of contents
This document is available on the World Wide Web as
Copyright 1995 by John David Stone (email@example.com)