Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 ยท Lists and Recursion

Recursion on Lists: Patterns

Master the list recursion template in Racket and Scheme: empty case, first and rest, sum, filter, map, append, reverse, nested lists and tree recursion.

A list is either empty or a first element followed by a smaller list. That sentence is the template for almost every list function you will write: handle the empty list, then handle the first element and recurse on the rest. Once you see the pattern, functions like sum, length, map, filter and append are variations on one theme.

All examples run on the stand-in interpreter and use only the core list functions.

The template

RACKET
(define (process lst)
  (cond [(null? lst) ...]                 ; empty list: the base case
        [else ... (first lst) ...         ; do something with the first element
              ... (process (rest lst)) ...])) ; recurse on the rest

Fill in the dots for each problem. The two questions to ask: what is the answer for an empty list? and how do I combine (first lst) with the answer for (rest lst)?

flowchart LR
    L["(a b c)"] --> F["first: a"]
    L --> R["rest: (b c)"]
    R --> P["process rest"]
    F --> C["combine"]
    P --> C

Split off the first element, recurse on the rest, combine.

Summing and counting

RACKET
(define (sum lst)
  (if (null? lst)
      0
      (+ (first lst) (sum (rest lst)))))

(define (my-length lst)
  (if (null? lst)
      0
      (+ 1 (my-length (rest lst)))))

The base answer for the empty list is 0 (the identity of addition). Another example, finding the largest element, needs a non-empty list as its base:

RACKET
(define (largest lst)
  (if (null? (rest lst))
      (first lst)
      (max (first lst) (largest (rest lst)))))
sum, length and largest

Building a new list

When the result is a list, cons the transformed first element onto the recursive answer:

RACKET
(define (double-all lst)
  (if (null? lst)
      '()
      (cons (* 2 (first lst)) (double-all (rest lst)))))

(define (keep-evens lst)
  (cond [(null? lst) '()]
        [(even? (first lst)) (cons (first lst) (keep-evens (rest lst)))]
        [else (keep-evens (rest lst))]))

double-all transforms every element (that is map); keep-evens keeps only some (that is filter). You will meet these as built-in functions in the next chapter, but writing them once yourself builds the intuition.

Transform and filter

Two lists at once: append

To join two lists, recurse on the first only; the second is returned untouched at the end:

RACKET
(define (my-append a b)
  (if (null? a)
      b
      (cons (first a) (my-append (rest a) b))))

Reverse with an accumulator

A naive reverse using append is slow: (append (rev (rest lst)) (list (first lst))) walks the growing list each time, giving quadratic time. With an accumulator, it is a single pass:

RACKET
(define (my-reverse lst)
  (let loop ([remaining lst] [acc '()])
    (if (null? remaining)
        acc
        (loop (rest remaining) (cons (first remaining) acc)))))

Each element is taken from the front of remaining and pushed onto the front of acc, which flips the order.

append and reverse

Nested lists and trees

If elements may themselves be lists, recurse on first as well as rest. This is tree recursion. Here is a function that counts all the non-list items (the "leaves") in a nested list:

RACKET
(define (count-leaves tree)
  (cond [(null? tree) 0]
        [(not (pair? tree)) 1]          ; a single item is one leaf
        [else (+ (count-leaves (first tree))
                 (count-leaves (rest tree)))]))

For '(1 (2 3) ((4))) it returns 4. The same shape flattens a tree:

RACKET
(define (flatten-tree t)
  (cond [(null? t) '()]
        [(not (pair? t)) (list t)]
        [else (append (flatten-tree (first t))
                      (flatten-tree (rest t)))]))
Tree recursion

A pattern cheat sheet

Goal Base case Combine
Sum / product / count 0 / 1 / 0 +, * with the first
Map (transform each) '() cons the transformed first
Filter (keep some) '() cons first only if it passes
Append the second list cons first onto recursive append
Reverse the accumulator push first onto accumulator
Search #f return first if it matches, else recurse

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the list template, what is the usual base case?

    Every list is either empty or a first element plus a smaller list, so the empty list is the base case.
  2. 2. What should (sum '()) return, and why?

    0 is the neutral element for +, so the sum of nothing is 0 and combining works for longer lists.
  3. 3. Why does the accumulator version of reverse run faster than one using append?

    The append version walks the growing list on every step, which makes it quadratic.
  4. 4. How does tree recursion differ from list recursion?

    When an element can itself be a list, the function must recurse into first as well as rest.

Summary

  • Almost every list function follows the template: empty case, then combine first with the recursion on rest.
  • Pick the base answer to match the operation (0 for sums, '() for new lists).
  • Use cons to build results; use an accumulator to reverse in one pass.
  • Tree recursion recurses on first and rest.

Next: Association Lists and Hash Tables