# 6  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?`.

## 6.1  `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.

## 6.2  Named `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.

## 6.3  Iteration

`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.

## 6.4  Mapping a procedure across a list

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)
```