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