2.3 · 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.

Lispex · SICP sourceScheme-compatible SICP syntax executed by the Lispex SICP profile.

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

Lispex learning runtimeLispex SICP profile 1.0.0

Loading Lispex SICP runtime

Lispex · SICP source269 / 1,048,576 UTF-8 bytes

Examples

Result—

Output: —
Value: —
Diagnostic: —

Visible execution0 / 0 trace events

This browser result is not a Lispex Vouch record or authority.wasm —

Expected observation

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 before you read the hint.

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 one hint

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