A procedure body can contain calls to other procedures, not least itself:
(define factorial (lambda (n) (if (= n 0) 1 (* n (factorial (- n 1))))))
This recursive procedure calculates the
factorial of a number. If the number is 0, the
answer is 1. For any other number n, the
procedure uses itself to calculate the factorial of
n ‑ 1, multiplies that subresult by n, and
returns the product.
Mutually recursive procedures are also possible. The following predicates for evenness and oddness use each other:
(define is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) (define is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1)))))
These definitions are offered here only as simple
illustrations of mutual recursion. Scheme already
provides the primitive predicates even? and
odd?.
letrec
If we wanted the above procedures as local
variables, we could try to use a let form:
(let ((local-even? (lambda (n) (if (= n 0) #t (local-odd? (- n 1))))) (local-odd? (lambda (n) (if (= n 0) #f (local-even? (- n 1)))))) (list (local-even? 23) (local-odd? 23)))
This won’t quite work, because the occurrences of
local‑even? and local‑odd? in the initializations
don’t refer to the lexical variables themselves.
Changing the let to a let* won’t work either,
for while the local‑even? inside local‑odd?’s body
refers to the correct procedure value, the local‑odd?
in local‑even?’s body still points elsewhere.
To solve problems like this, Scheme provides the form
letrec:
(letrec ((local-even? (lambda (n) (if (= n 0) #t (local-odd? (- n 1))))) (local-odd? (lambda (n) (if (= n 0) #f (local-even? (- n 1)))))) (list (local-even? 23) (local-odd? 23)))
The lexical variables introduced by a letrec are
visible not only in the letrec-body but also within
all the initializations. letrec is thus
tailor-made for defining recursive and mutually
recursive local procedures.
let
A recursive procedure defined using letrec can
describe loops. Let’s say we want to display a
countdown from 10:
(letrec ((countdown (lambda (i) (if (= i 0) 'liftoff (begin (display i) (newline) (countdown (- i 1))))))) (countdown 10))
This outputs on the console the numbers 10 down to
1, and returns the result liftoff.
Scheme allows a variant of let called named
let to write this kind of loop more compactly:
(let countdown ((i 10)) (if (= i 0) 'liftoff (begin (display i) (newline) (countdown (- i 1)))))
Note the presence of a variable identifying the loop
immediately after the let. This program is
equivalent to the one written with letrec. You may
consider the named let to be a macro
(chapter 8) expanding to the letrec form.
countdown defined above is really a recursive
procedure. Scheme can define loops only through
recursion. There are no special looping or iteration
constructs.
Nevertheless, the loop as defined above is a genuine loop, in exactly the same way that other languages bill their loops. I.e., Scheme takes special care to ensure that recursion of the type used above will not generate the procedure call/return overhead.
Scheme does this by a process called tail-call
elimination. If you look closely at the countdown
procedure, you will note that when the recursive call
occurs in countdown’s body, it is the tail call,
or the very last thing done — each invocation of
countdown either does not call itself, or when it
does, it does so as its very last act. To a Scheme
implementation, this makes the recursion
indistinguishable from iteration. So go ahead, use
recursion to write loops. It’s safe.
Here’s another example of a useful tail-recursive procedure:
(define list-position (lambda (o l) (let loop ((i 0) (l l)) (if (null? l) #f (if (eqv? (car l) o) i (loop (+ i 1) (cdr l)))))))
list‑position finds the index of the first
occurrence of the object o in the list l. If
the object is not found in the list, the procedure
returns #f.
Here’s yet another tail-recursive procedure, one that reverses its argument list “in place”, i.e., by mutating the contents of the existing list, and without allocating a new one:
(define reverse! (lambda (s) (let loop ((s s) (r '())) (if (null? s) r (let ((d (cdr s))) (set-cdr! s r) (loop d s))))))
(reverse! is a useful enough procedure that it is
provided primitively in many Scheme dialects, e.g.,
MzScheme and Guile.)
In the last chapter, we defined two procedures throw‑one‑die
and throw‑two‑dice that returned the result of a single
experiment, i.e., a single throw of one or two dice. What if we
want to find the expected result, and we don’t want to do the
calculations? One way, the so-called Monte Carlo method, is to
use iteration to
run the experiment many (e.g., 10000) times, and average the results.
(define *num-trials* 10000) (define monte-carlo (lambda (experiment) (let loop ((i 0) (acc 0.0)) (if (= i *num-trials*) (/ acc *num-trials*) (loop (+ i 1) (+ acc (experiment)))))))
Now run
(monte-carlo throw-one-die) => 3.4728 (monte-carlo throw-two-dice) => 6.9994
The expected values should be close to 3.5 and 7 respectively.
For some numerical-calculus examples of recursion (including iteration), see appendix C.
A special kind of iteration involves repeating the same
action for each element of a list. Scheme offers two
procedures for this situation: map and for‑each.
The map procedure applies a given procedure to every
element of a given list, and returns the list of the
results. E.g.,
(map add2 '(1 2 3)) => (3 4 5)
The for‑each procedure also applies a procedure to each
element in a list, but returns void. The procedure
application is done purely for any side-effects it may
cause. E.g.,
(for-each display (list "one " "two " "buckle my shoe"))
has the side-effect of displaying the strings (in the order they appear) on the console.
The procedures applied by map and for‑each
need not be one-argument procedures. For example,
given an n-argument procedure, map
takes n lists and applies the procedure to
every set of n of arguments selected from across
the lists. E.g.,
(map cons '(1 2 3) '(10 20 30)) => ((1 . 10) (2 . 20) (3 . 30)) (map + '(1 2 3) '(10 20 30)) => (11 22 33)