2.2.2 · Hierarchical data

The recursion follows the shape of the data.

A tree asks the same question at every node. Is this empty, another pair to explore, or a leaf to transform?

Guiding question

How does one procedure work across every depth of a tree?

Recognize leaf and branch cases
Rebuild a tree while preserving its shape
Use structural recursion instead of fixed depth

scale-tree does not count levels. When it finds a pair, it applies the same procedure to both parts. When it finds a leaf, it performs the numeric work.

The control structure mirrors the data definition. That correspondence is why the procedure works for a shallow list and a deeply nested tree without separate cases for each depth.

SICP code269 of 1,048,576 UTF-8 bytes

(begin
  (define (scale-tree tree factor)
    (cond ((null? tree) '())
          ((pair? tree)
           (cons (scale-tree (car tree) factor)
                 (scale-tree (cdr tree) factor)))
          (else (* tree factor))))
  (scale-tree '(1 (2 (3 4) 5) (6 7)) 10))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (10 (20 (30 40) 50) (60 70)).

Trace focus

Find where the process branches into car and cdr work. The final nesting is a record of those repeated structural decisions.

Try it yourself

Change the program and compare the result.

Define count-leaves. It should return 0 for the empty list, add both branches for a pair, and return 1 for any other leaf.

Show hint

Use the same three-way classification as scale-tree but change the leaf operation.

Complete this lesson

0 of 20 lessons complete in this chapter0%