# 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 laguages 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 . ("Hello" . ???)))))
```

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 functon which computes \(a^n\) using a *for* loop. (NB: this is a naïve 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 Why 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 entertainement 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)))))
```