Lesson 3: Recursion, Iteration, and Growth

Goal

After this lesson you should be able to estimate whether a small list procedure does one pass or nested work, recognize a tail call, write an accumulator-style loop, and explain why Scheme can use procedure calls for iteration.

This lesson is about efficiency, but only at the level needed for the rest of the course. We are not measuring hardware, compilers, or wall-clock time. We are learning how the shape of a program affects the amount of work it asks Scheme to do.

Counting Work, Not Machines

For small examples, a program that is clear is usually better than a program that is only a little faster. Still, some differences are structural. If a procedure does one multiplication for every item in a list, doubling the list roughly doubles that work. If a procedure compares each item against many other items, doubling the list may more than double the work.

We use order-of-growth notation for this rough estimate:

O(1) means the work stays bounded by a constant as the input grows.
O(N) means the work grows in proportion to the input size.
O(N^2) means the work grows roughly with the square of the input size.
O(2^N) means the work doubles with each added step of input size.

This notation deliberately ignores constant factors and small inputs. The point is not to predict an exact time. The point is to see what happens when the input becomes large.

One Pass Over a Proper List

A proper list is either empty or has a first element and a rest. That shape gives a natural recursive program.

(define (square-number n)
  (* n n))

(define (square-list numbers)
  (if (null? numbers)
      '()
      (cons (square-number (car numbers))
            (square-list (cdr numbers)))))

For a list with N numbers, square-list calls square-number once for each number. The result is O(N) time.

Try this expression

This procedure also builds a new list of N numbers, so the result itself uses O(N) space. That is separate from the control space used while evaluating the recursive calls.

A Quadratic Example

Insertion sort is a compact example where one recursive procedure uses another recursive procedure.

(define (insert-sorted n sorted)
  (cond
    ((null? sorted) (list n))
    ((<= n (car sorted)) (cons n sorted))
    (else (cons (car sorted)
                (insert-sorted n (cdr sorted))))))

(define (insertion-sort numbers)
  (if (null? numbers)
      '()
      (insert-sorted (car numbers)
                     (insertion-sort (cdr numbers)))))

insert-sorted may have to walk across the whole sorted list. If there are K elements in that list, the insertion can require about K comparisons.

insertion-sort performs insertions into lists of increasing size. In the worst case, the comparison count has this shape:

0 + 1 + 2 + ... + (N - 1)

That sum grows like N^2, so this insertion sort is O(N^2) time.

Try this expression

This does not mean insertion sort is useless. It is short, clear, and reasonable for small lists. The lesson is that the shape of the work is different from a one-pass list procedure.

Recursive Process and Pending Work

A direct recursive count is easy to read:

(define (count-list items)
  (if (null? items)
      0
      (+ 1 (count-list (cdr items)))))

The recursive call is not the final action. After (count-list (cdr items)) returns, Scheme still has to add 1.

For a three-element list, the pending work has this shape:

(count-list '(a b c))
(+ 1 (count-list '(b c)))
(+ 1 (+ 1 (count-list '(c))))
(+ 1 (+ 1 (+ 1 (count-list '()))))
(+ 1 (+ 1 (+ 1 0)))
3

This is a linear recursive process. It uses O(N) time and also keeps O(N) pending additions in control space.

Try this expression

Tail Recursion with an Accumulator

Now write the same count with a helper procedure that carries the current answer forward.

(define (count-list-tail items)
  (define (loop rest count)
    (if (null? rest)
        count
        (loop (cdr rest) (+ count 1))))
  (loop items 0))

The recursive call to loop is in tail position: its value is immediately the value of the surrounding branch. There is no pending (+ 1 ...) waiting after the call returns.

The process has this shape:

(count-list-tail '(a b c))
(loop '(a b c) 0)
(loop '(b c) 1)
(loop '(c) 2)
(loop '() 3)
3

The extra parameter count is an accumulator. It holds the partial result accumulated so far.

Try this expression

Proper Tail Recursion

R7RS Scheme requires proper tail recursion. That means an implementation must execute a tail call without keeping an unbounded chain of control frames for earlier calls.

This is why Scheme programmers can use recursive calls for loops. A tail-recursive procedure can run as an iterative process.

Be precise about what this saves. Tail recursion saves control space for the calls. It does not make the result free. A procedure that builds a list of N results still needs space for those N result pairs.

For example, a tail-recursive square-list can carry the answer in reverse order, then reverse it at the end:

(define (square-list-tail numbers)
  (define (loop rest out)
    (if (null? rest)
        (reverse out)
        (loop (cdr rest)
              (cons (* (car rest) (car rest)) out))))
  (loop numbers '()))

This loop does not need a growing chain of pending procedure calls, but the result list still has one element for each input element.

Try this expression

Repeated Work

Some recursive programs are simple but repeat the same work many times. Pascal's triangle is a useful example. Rows and columns start at 0; row 4 is 1 4 6 4 1.

(define (pascal row col)
  (cond
    ((or (< col 0) (> col row)) 0)
    ((or (= col 0) (= col row)) 1)
    (else (+ (pascal (- row 1) (- col 1))
             (pascal (- row 1) col)))))

This definition follows the mathematical rule directly: an inside entry is the sum of the two entries above it. But it recomputes many entries. The same smaller Pascal values are requested again and again.

A row-building version does more visible bookkeeping, but it avoids much of that repeated work.

(define (next-pascal-row row)
  (define (loop rest out)
    (if (null? (cdr rest))
        (reverse (cons 1 out))
        (loop (cdr rest)
              (cons (+ (car rest) (cadr rest)) out))))
  (loop row '(1)))

(define (pascal-row row-number)
  (define (loop row index)
    (if (= index row-number)
        row
        (loop (next-pascal-row row) (+ index 1))))
  (loop '(1) 0))

The direct definition is good for explaining the rule. The row-building definition is better when the row is larger. More code can mean less repeated work.

Try this expression

First Complete Example

The published example source for this lesson checks linear list traversal, direct and tail-recursive counting, insertion sort, a tail-recursive list builder, and two Pascal implementations.

(define (count-list-tail items)
  (define (loop rest count)
    (if (null? rest)
        count
        (loop (cdr rest) (+ count 1))))
  (loop items 0))

(define (insertion-sort numbers)
  (if (null? numbers)
      '()
      (insert-sorted (car numbers)
                     (insertion-sort (cdr numbers)))))

The full source file has a highlighted view at /examples/r7rs/intro/lesson-03/ and a raw source link from that page.

When working from the source tree used to build this site, run the example suite with:

scripts/test_examples_chicken.sh

Exercises

These exercises are original and deliberately small.

For (square-list '(2 3 4 5)), how many multiplications are performed?
Write double-list, a one-pass procedure that doubles each number in a proper list.
Explain why count-list has pending work after the recursive call returns.
Trace (count-list-tail '(x y z)) as a sequence of loop calls.
Define sum-list-tail using an accumulator.
Use insert-sorted by hand to insert 4 into '(1 3 5 7).
Sort '(3 1 2) by hand using the insertion-sort structure.
Compute (pascal 4 2) from the direct definition, then compare it with (list-ref (pascal-row 4) 2).
Identify one example in this lesson that uses O(N) time and one that uses O(N^2) time.
Explain why tail recursion saves control space but does not remove the space needed for a result list.

What Comes Next

The next lesson is Lesson 4: data abstraction and pair diagrams. It uses pairs and lists from the previous lessons to separate a data type's meaning from its representation.

Before moving on, make sure you can explain these ideas without guessing:

Why square-list is O(N).
Why insertion sort is O(N^2) in the worst case.
What pending work means in a recursive process.
Why count-list-tail is tail-recursive.
What R7RS proper tail recursion guarantees.
Why a program that appears to do more bookkeeping can still be faster by avoiding repeated work.