Table of Contents
< 7. First-Class Functions 9. API Reference >

8. Recursion

If functions returning functions wasn't enough of a mind bender, consider a function that calls itself. It's called a recursive function.

Recursion means defining something in terms of itself. Of course, at some point, we wish the computation to stop. Therefore, in every call to itself, a recursive function must somehow become smaller or lead to a fixed, final goal value.

Adding a sequence of numbers

Consider a sequence of whole numbers starting from 1, such as 1, 2, 3, 4, 5. First of all, we can start adding left-to-right, like 1 + 2 + 3 + 4 + 5, or right-to-left, like 5 + 4 + 3 + 2 + 1.

It is preferable to start with the largest number, because you should always think of recursive steps making things smaller.

(define (add-sequence n)
  (if (= n 0)
      0
      (+ n (add-sequence (- n 1)))))

The smallest, and trivial case, is adding 0. The return value should be 0. We use the if special form to signal the end of the recursion.

Now, let's say n is 5, to solve the addition shown above. What does the following return?

(add-sequence 5)

Breaking down the computation step-by-step, we have:

;; (add-sequence 5)
  (if (= 5 0)
      0
      (+ 5 (add-sequence (- 5 1))))

Clearly 5 is not 0, so we take the else branch, which is

(+ 5 (add-sequence (- 5 1)))

which is

(+ 5 (add-sequence 4))

Repeating the same logic, the next step is

(+ 5 (+ 4 (add-sequence 3)))

And so on until n is 0:

(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 (add-sequence 0))))))

We finally get a true value for (if (= 0 0) ...), meaning

(add-sequence 0)

is 0.

The final result, computed manually, is:

(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))

which is 15.

If we pass a negative number to add-sequence, it will crash, because we were assuming positive numbers are to be added. n is decreased by 1 in each step, and we only check if it equals 0. A negative number only becomes more negative after each step.

Using <= instead of = is a possible solution, but can be misleading because negative numbers can be added, but the function will return 0. It really depends on what you and the user wishes to accomplish.

Compared to an imperative language, which often relies on reassigning variables to new values, the recursion above seems excessively complex. But from a mathematical standpoint, if each step is sufficiently complex, recursion will result in cleaner and easier to follow code than alternative code using loops and assignments.

The Sierpinski triangle

To end this chapter, let's see how a recursive definition can be used to generate the Sierpinski triangle.

It starts by creating an outer triangle, dividing it into four parts, and drawing itself in each of the three right-side-up triangles. Try to draw a triangle that is too small is the signal to stop our recursion, because we won't even be able to see anything smaller than a few pixels.

A right triangle is used to simplify the geometrical calculations (the triangle draws itself from the midpoints of each edge). Coordinates for the midpoints in an equilateral triangle would have involved many more calculations.

The special forms let and let* are used to define temporary variables, to avoid re-typing the same values over and over again, and begin is used to wrap a sequence of actions in the else branch of if.

(define (triangle x y side)
  ;; draw three sides with points a, b, and c
  (let ((ax x)
        (ay y)
        (bx (+ x side))
        (by y)
        (cx x)
        (cy (+ y side)))
    (line ax ay bx by)
    (line ax ay cx cy)
    (line cx cy bx by)))

The outer triangle is:

(triangle -170 -170 340)
(define (sierpinski x y side)
  (let* ((half-side (/ side 2))
         (midpt-ax x)
         (midpt-ay (+ y half-side))
         (midpt-bx (+ x half-side))
         (midpt-by y))
    (if (< side 10)  ; stop at 10 pixels
        "done"
        (begin
          (triangle x y side)
          (sierpinski x y half-side)
          (sierpinski midpt-ax midpt-ay half-side)
          (sierpinski midpt-bx midpt-by half-side)))))
(clear)
(sierpinski -170 -170 340)
< 7. First-Class Functions 9. API Reference >
Table of Contents