# Recursion#

If you made it so far, you likely wondered when I would introduce the syntax for loops. In so-called imperative languages, a family of languages comprising most highly popular languages like Python, C, C++, Java, PHP, etc., there are almost always two types of loops, „while“ and „for“. Scheme is different. Although these loops do exist, under somewhat unusual forms, they are seldom used. Scheme embraces the functional programming paradigm, which entails that the typical way of iterating operations is to write recursive functions. Instead of a simple „for“ loop, you thus need to write an „auxiliary tail-recursive function with an accumulator“, which is fortunately not as hard as the name makes it sound like.

## How recursion works#

Let us try to write a function taking a parameter \(n\) and printing the integers from \(n\) to 0, in descending order. For example, a possible implementation of this function in Python would be:

```
def print_descending_integers(n):
for i in reversed(range(n+1)):
print(i)
```

Even though remote equivalents to `for`

do exist in Scheme, the typical way of
doing it is different. Imagine you’re stuck writing this function, and somewhat
stupidly, you start by just printing the first integer.

```
(define (print-descending-integers n)
(display n) (newline)
???)
```

You now need to print the remaining integers, from \(n-1\) to 0. But… you have a
function for that! It’s the very function `print-descending-integers`

you are
defining. Let’s try:

```
(define (print-descending-integers n)
(display n) (newline)
(print-descending-integers (1- n)))
```

(If you forgot about `1-`

, it is mentioned in Expressions.)

If you execute `(display-descending-integers 5)`

, you will get:

```
⊨ 5
⊨ 4
⊨ 3
⊨ 2
⊨ 1
⊨ 0
⊨ -1
⊨ -2
⊨ -3
⊨ -4
⊨ -5
⊨ -6
⊨ x-7
...
```

This is because the function calls itself, and this process has no reason to stop. We actually forgot a detail. If \(n\) is 0, the function shouldn’t continue with -1, since we only wanted to print integers down to 0. We therefore need to add a condition to avoid this infinite loop.

```
(define (display-descending-integers n)
(display n) (newline)
(if (not (= n 0))
(display-descending-integers (1- n))))
```

This time, the result is as expected:

```
(print-descending-integers 5)
⊨ 5
⊨ 4
⊨ 3
⊨ 2
⊨ 1
⊨ 0
```

The definition of a recursive function is a function that *calls itself*.
Recursion is one instance of a technique called „divide and conquer“, which
consists in solving a problem by breaking it into smaller pieces, solving those
subproblems, then finally assembling the pieces together. In this case, the
problem „display integers from \(n\) to \(0\)“ is being broken into „display \(n\)“
and „display integers from \(n-1\) to \(0\)“. The first of these subproblems is easy
to solve, and the second one can be solved using a recursive call. You always
need to consider the base cases, those with the smallest instances of the
problem, which here means \(n = 0\), in order to avoid infinite recursion.

## More on lists#

Now is the time to reveal the secret of Scheme lists.

Lists *do not exist*.

They simply do not exist! There are only *pairs*.

Suppose you want to fit the elements of the list `'(0 1 2 3 "Hello")`

in a pair.
Dumbly (but in fact intelligently, like above), you could start with putting the
first element in the pair’s *car*.

```
'(0 . ???)
```

You still have 4 elements to fit, but only a *cdr* to store them. Here comes the
core idea. You just need to put them … in a new pair!

```
'(0 . (??? . ???))
```

In this new pair, you have room for a new element, in the *car*.

```
'(0 . (1 . ???))
```

Again, the *cdr* will be a pair, of which the *car* will be the next element.

```
'(0 . (1 . (2 . ???)))
```

Continuing:

```
'(0 . (1 . (2 . (3 . ("Bonjour" . ???)))))
```

All elements of the list have now found their place in the *car* of a pair. You
just need to fill the remaining *cdr* of the last pair. It corresponds to the
base case, the case of a zero-element list. This is just the empty list, `'()`

.
Finally, the result is:

```
'(0 . (1 . (2 . (3 . ("Hello" . ())))))
```

Nested pairs like this are automatically detected and printed as lists. These lists are in fact just pairs. Lists only exist by convention, as pairs of pairs of …

```
'(0 . (1 . (2 . (3 . ("Hello" . ())))))
⇒ (0 1 2 3 "Hello")
```

Thus, a list is a pair. Its *car* is its first element. Its *cdr* is the list of
remaining elements. There is the special case of the empty list, which is not a
pair. It’s just a constant, which can be compared with `eq?`

, like symbols. This
definition of lists is recursive: a list is either the empty list, or a pair of
an element and a list. It is naturally suited for writing recursive functions.

For example, you can implement the `filter`

function as a recursive function as
follows. The parameters will be `function`

(the function that decides whether an
element should be kept), and `lst`

(the list to be filtered).

If

`lst`

is the empty list,`filter`

obviously returns the empty list. This is the base case.Else,

`lst`

is a pair of its first elements and the list of the remaining elements. You can start by applying the filtering with the list of remaining elements, which solves the subproblem. Then, call`function`

on the first element. If`function`

returns true, the element should be added to the filtered sublist. Else, it shouldn’t be added. This way, the problem has been solved using the solution of the subproblem.

Here is this definition in code:

```
(define (filter2 function lst)
(if (null? lst)
'()
(let* ((first-element (car lst))
(remaining-elements (cdr lst))
(filtered-rest (filter2 function remaining-elements)))
(if (function first-element)
(cons first-element filtered-rest)
filtered-rest))))
(filter2 even? '(0 1 2 3 4 5)
⇒ (0 2 4)
```

The test `(eq? lst '())`

is so frequent that it can be abbreviated as
`(null? lst)`

.

## Tail recursion#

Although not strictly necessary for usual programming, this part will be useful if you are looking to understand functional programming or write really efficient code.

Let’s work on the problem of computing integer powers. If you remember of your math courses in the good old times, \(a^n\) is defined as \(\underbrace{a \times a \times \cdots \times a}_\text{n times}\).

Here is a Python function which computes \(a^n\) using a *for* loop. (NB: this is
a naive algorithm; it would be much faster to use
exponentiation by squaring.)

```
def power(a, n):
result = 1
for i in range(n):
result = result*a
return result
```

In Scheme, the idiomatic style is again to break up the problem. For that,
remark that if you already computed \(a^{n-1}\), you can multiply by \(a\) one last
time to get \(a^n\). This is easily seen on the definition:
\(a^n = \underbrace{a \times a \times \cdots \times a
\times a}_\text{n times} = \underbrace{a \times a \times \cdots \times
a}_\text{n-1 times} \times a\).
The base case is \(a^0 = 1\), which corresponds to how the `result`

variable was
initialized to 1 in the Python function. Here is the Scheme recursive function:

```
(define (power a n)
(if (= n 0)
1
(* a (power a (1- n)))))
```

There is a problem with this, however. This Scheme function consumes much more memory than the Python function. In my experiments, computing \(2^{300\,000}\) required roughly 10MiB memory with the Python function, but 40MiB for the Scheme function.

To understand why, you need to make yourself a mental model of how `power`

is
executed. As an example, consider the call `(power 2 5)`

.

The interpreter begins the call,

`(power 2 5)`

. Since \(5 \neq 0\), it evaluates`(* 2 (power 2 4))`

.It continues with the subexpression

`(power 2 4)`

, which in turn calls`(power 2 3)`

.This continues until

`(power 2 1)`

calling`(power 2 0)`

.`(power 2 0)`

returns 1, which is substituted in`(power 2 1)`

.`(power 2 1)`

now got all the ingredients to produce its result and returns 2.This continues until

`(power 2 4)`

.`(power 2 4)`

yields 16 to`(power 2 5)`

, which finally returns 32.

At the time it ran `(power 2 0)`

, the interpreter had to remember all the
previous calls, because they weren’t finished yet. Consequently, the *call
stack* above the root call `(power 2 5)`

grew to a size of 5 before decreasing
to 0. Had we taken \(n = 300\,000\), the stack would have grown to a size of
\(300\,000\). On the other hand, the Python program just has a *for* loop. The
call stack never grows.

This issue with the size of the call stack may not be all that pressing in Guile
2.2, as it is just a bit of memory wasted. It is pressing, however, in Guile
1.8, or in other functional languages. (Go back to Warum überhaupt Scheme? to know what
your version of Guile is.) This is because, due to the way the call stack is
often implemented, its size is very limited. In Guile 1.8, this `power`

function
won’t be able to compute \(a^n\) for \(n\) past a few tens of thousands. What is
worse, it will likely end in an completely uninformative error message such as
„Segmentation fault (core dumped)“, or, in Frescobaldi, „Exited with return code
11“.

Our first recursive program did not have this problem. To understand why, observe where the recursive call is placed.

```
(define (display-descending-integers n)
(format #t "~a\n" n)
(if (not (= n 0))
(display-descending-integers (1- n))))
```

When the execution of `display-descending-integers`

reaches the recursive call,
there is no longer anything else to do. For this reason, there is no point in
keeping the call on the call stack. Think of an annoying administration asking
you: „go sign the form at the secretarial office on the third floor and come
back here with it“. Assume that the secretarial office on the third floor asks
you to go in turn do something at a desk on the sixth floor and come back, and
on the sixth floor you are asked to go to the director’s office at the eighth
floor and come back. When you arrive at the director’s office, you need to
remember the location of the desk on the sixth floor, the secretarial office on
the third floor and the reception desk, because you will need to come back to
them. On the other hand, if every of these levels just asks you to go somewhere
else but not to come back afterwards, you don’t need to remember anything. After
getting the ardently desired document from the director, you can go out of the
building, and you may have already forgotten that the desk on the sixth floor
was number 40B, and that you had been sent there from the secretarial office 26
from the third floor where you went on the advice of the reception desk number
4.

This clever recursion is called *tail recursion*. It happens when a function
ends its execution by returning the value of a call to another function. In this
case, the interpreter can forget about the current call, and continue with the
subcall. In technical terms, forgetting about the current call means that its
stack frame is simply replaced with a new stack frame for the tail call, instead
of adding a new stack frame for the tail call on top of the current call. That
way, the stack depth remains constant instead of growing. The Scheme
specification mandates that implementations optimize tail recursion in this way.

We’re going to transform the code of this `power`

function so it becomes
tail-recursive. As a reminder, this was its code:

```
(define (power a n)
(if (= n 0)
1
(* a (power a (1- n)))))
```

The game is to do without multiplying the result of the recursive call to
`power`

by `a`

. Because you need to multiply by `a`

somewhere, the idea that
works is to do it *before* calling `power`

, and to incorporate the result
*inside* the call to `power`

. Instead of asking for the value of \(a^{n-1}\) and
multiplying it by \(a\), the function will multiply a partial result by \(a\), and
hand this partial result to a recursive call.

```
(define (partial-power a n r)
(if (= n 0)
r
(partial-power a
(1- n)
(* a r))))
```

This `partial-power`

function takes an extra argument, `r`

, the partial result,
also called the *accumulator*. When \(n\) reaches 0, the function ends the cycle
of recursive calls and returns the partial result it received, which is in fact
the end result. Else, it calls itself in a tail call fashion. The `a`

parameter
remains unchanged. `n`

is lowered by 1, as the number of iterations remaining to
do is reduced by 1, and `r`

is multiplied by `a`

.

Since the function that the user expects only takes two arguments, `a`

and `n`

,
the code can be completed with a `power`

function which just calls
`partial-power`

with 1 for `r`

(the base case).

```
(define (power a n)
(partial-power a n 1))
```

Now, you understand why the `power`

function is said to use an „auxiliary
tail-recursive function with accumulator“.

However, the `partial-power`

function is only ever used within `power`

. It is
more convenient to define it inside `power`

, which gets rid of the `a`

parameter. (To avoid having two different things called `n`

in the same
function, it is wiser to rename the `n`

parameter of `partial-power`

, for
example as `i`

.)

```
(define (power a n)
(define (partial-power i r)
(if (= i 0)
r
(partial-power (1- i)
(* a r))))
(partial-power n 1))
```

## Named `let`

syntax#

It is common to define an auxiliary recursive function (preferably
tail-recursive). In most instances, this function is only ever called once, just
after having been defined. For this frequent case, Scheme provides a simpler
syntax called „named let“. It is sort of a mix between `let`

and `define`

.
Before turning to how a named let is written, let us first note that `let`

is a
convenience for what could equally be spelt as a function call. These are
equivalent:

```
(let ((variable1 value1)
(variable2 value2)
...)
expressions ...)
```

and

```
(define (some-function-name variable1 variable2 ...)
expressions ...)
(some-function-name value1 value2 ...)
```

This may be confusing at first. To understand why these are equivalent, try to
change your point of view on the `let`

construct. Indeed, it is a way of giving
names to values so you can reuse them. However, if you focus not on the
variables but on the body of the `let`

(the `expressions ...`

part above), you
can view it as a computation that has variadic parts – the variables. Remember
that a function is something similar – it has a body with variadic parts, the
function parameters, and executing the function also binds the arguments passed
to the function to the respective parameters before executing the body in a way
that makes these parameters available.

(It is a little white lie to claim that these two forms are completely
equivalent, since a `define`

form is not valid everywhere, see
Local variables.)

So far, this way of rewriting a `let`

expression using a function definition may
look like a mere entertainment for theoretical computer scientists. (In fact, it
has theoretical importance, given that Scheme is originally based on
lambda calculus, where there is
no way of binding variable other than using lambda functions.) It is however
easier to understand how named let works if you firmly understand it. The idea
of named let is that is allows you to reuse the function that appears in the
translation of `let`

within the body of the `let`

expression. This is the
syntax:

```
(let function-name ((variable1 value1)
(variable2 value2))
expressions ...)
```

This type of `let`

is evaluated like a normal `let`

, but with an added feature.
Within the expressions in the `let`

body, the variable `function-name`

is bound
to the function that would be defined in the other form of `let`

with `define`

.
When this other form was introduced above, it was implicit that the name
`some-function-name`

was arbitrary, and not reused inside the function itself.
With a named let, this becomes possible. The `let`

above would translate into

```
(define (function-name variable1 variable2 ...)
expressions ...)
(function-name value1 value2 ...)
```

Thus, as soon as you are writing an auxiliary recursive function, and you only
define it in order to call it directly, you can use named let syntax. As a
reminder, the last version of our `power`

function was:

```
(define (power a n)
(define (partial-power i r)
(if (= i 0)
r
(partial-power (1- i)
(* a r))))
(partial-power n 1))
```

Here is how this function can be rewritten with a named let:

```
(define (power a n)
(let partial-power ((i n)
(r 1))
(if (= i 0)
r
(partial-power (1- i)
(* a r)))))
```

This style is idiomatic in Scheme.

To conclude, here is a new implementation of `filter`

. This one is
tail-recursive, and written using a named let. The accumulator is built by
adding elements at the front of the list using `cons`

, so it needs to be
reversed before returning it.

```
(define (filter3 function lst)
(let loop ((rest lst)
(acc '()))
(if (null? rest)
(reverse acc)
(loop (cdr rest)
(if (function (car rest))
(cons (car rest)
acc)
acc)))))
```