Recursion

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
(chap 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. Ie, 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”, ie, 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, eg,
MzScheme and Guile.)

For some numerical 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. Eg,

(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. Eg,

(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. Eg,

(map cons '(1 2 3) '(10 20 30))((1 . 10) (2 . 20) (3 . 30)) (map + '(1 2 3) '(10 20 30))=>(11 22 33)=>